Linked Questions

1
vote
1answer
129 views

Examples of wrong proof by induction [duplicate]

Could someone provide a wrong clime and its wrong proof by induction so that only the first step be wrong?
90
votes
10answers
17k views

Surprise exam paradox?

I just remembered about a problem/paradox I read years ago in the fun section of the newspaper, which has had me wondering often times. The problem is as follows: A maths teacher says to the class ...
32
votes
6answers
22k views

Questions on “All Horse are the Same Color” Proof by Complete Induction

I'm bugged by the following that's summarized on p. 109 of this PDF. False theorem: All horses are the same color. Proof by induction: $\fbox{$P(n)$ is the statement: In every set of ...
4
votes
5answers
5k views

Prove by induction that $n^3 + 11n$ is divisible by $6$ for every positive integer $n$.

Prove by induction that $n^3 + 11n$ is divisible by $6$ for every positive integer $n$. I've started by letting $P(n) = n^3+11n$ $P(1)=12$ (divisible by 6, so $P(1)$ is true.) Assume $P(k)=k^3+11k$ ...
0
votes
1answer
685 views

Finding the error in this induction proof [duplicate]

Claim: If $n$ belongs to $\mathbb{N}$, and $p$ and $q$ are natural numbers with maximum $n$, then $p=q$. Let $S$ be the subset of the natural numbers for which the claim is true. $1$ belongs to $S$, ...
0
votes
1answer
255 views

Mathematical Induction. Horses made me question my understanding [duplicate]

I recently read about the false inductive proof that all horses are the same colour. There are some mathSE threads about this already (MathSE_thread_1, MathSE_thread_2). After reading this, I now ...
2
votes
3answers
115 views

Proving $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$ using strong induction

The question says $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$. Here is my proof by strong induction: Base case: $10\cdot0=0$. Let $k\geq 0$, and suppose that for any $m\leq k$ we have ...
0
votes
2answers
97 views

How does $( 1 - (1- \frac{1}{2^{2^k}}))$ become $(1+ \frac{1}{2^{2^k}})$?

How does $\left( 1 - \left(1- \frac{1}{2^{2^k}}\right)\right)$ become $\left(1+ \frac{1}{2^{2^k}}\right)$? I distributed the former but got negative $-\frac{1}{2^{2^k}}$. So it does not match the ...
0
votes
2answers
92 views

Evaluate $\lim_{n\to\infty}\left(\sqrt{\frac{9^n}{n^2}+\frac{3^n}{5n}+2}-\frac{3^n}{n}\right)$

Find, if it exists, the following limit: $\displaystyle\lim_{n\to\infty}\left(\sqrt{\frac{9^n}{n^2}+\frac{3^n}{5n}+2}-\frac{3^n}{n}\right)$.
0
votes
3answers
98 views

Proving ${\sum}^n _{i=1}i = \frac {n(n+1)}{2}$ by induction

I am having problems understanding how to 'prove' a summation formula. I have the equation: $ {\sum}^n _{i=1}i = \frac {n(n+1)}{2} $ Basis Step when: $ n=1 $ $ {\sum}^1 _{i=1}i = \frac {1(1+1)}{...
1
vote
0answers
123 views

The pencils in a box of crayons always have the same color [duplicate]

I retrieved an old math book and I'm delighted to share following exercise. The pencils in a box of crayons always have the same color. Proof by induction on the number $n$ of pencils in the box: ...