# so Thinking about induction proofs

So I'm studying some induction proofs, but I have some questions that were not clear to me when I read the book's definition.

I want to know if my understanding is correct:

So, for me, and induction proof works like this:

1. I don't exactly need to check if the equations is true for $k = 1$. If I check it it for $k=12$ for example, then the formula will be true for every natural number greater than $12$: $13, 14, 15, 16,...$. But of course it's better to check for $n=1$ so I'll have proven the formula for all natural numbers. But this aspect is important for my understanding, because of the second step:
2. If I assume that the formula is true for $k$, and based on the validity of the $k$ case, I know that it will be true also for $k+1$.So the heart of an induction proof is in the fact that I can, then, prove that the formula is true for $k$, so the consequence will be that the formula is true for $k+1$.
3. Ok, so I assumed that the formula is true for $k$ and then used the fact that if it is true, then $k+1$ is true. So if I let $k = 12$ (and check that the formula is indeed true for $k=12$), then the formula is valid for $k=13$, because if $k$ is true (and for $k=12$ it is) then the formula is true for $k+1$ that is $13$. Great, now I know that the formula works for $k=12$ and $k=13$. So I can use the same logic again: I know that if the formula is true for $k$, then it's true for $k+1$. So instead of using $k=12$, I also now that the formula works for $k=13$, so I can plug this value instead, then the formula will be valid for $k=13+1 = 14$ as well. So now I can do the exaclty same thing: plug $k=14$ and then the formula is true for $k=14+1 = 15$. I could do this forever, and would always be true, so the formula works for every natural number greater than or equal to $12$.
4. I could let $k=1$ and then I would have proven it for all the natural numbers, or I could check the formula for $k=1,2,...,12$ manually, and then let $k=12$ be the first domino.

Conclusion: the heart of na induction proof lies in the fact that I can assume it is true for $k$, and if it's true for $k$, then it will be true for $k+1$. I can, then, show that it's true for a particular value $k=12$ for example, then I proved that it's true for $13$. Now I can forget completely what I've done. I know that it's true for $13$, so if $13$ was the choosen $k$, then it would be correct for $14$. It can be done forever.

-
Not always you can start from $n=1$, for instance, $n! > 3^n$ is true for $n > 6$. In this case, your base case would be with $n=7$. –  Nigel Overmars Apr 14 '14 at 20:23
@NigelOvermars yep, this is also something good to remember! –  Marter Js Apr 14 '14 at 20:24
Well, regarding your conclusion: At the heart of the induction proof lies, I think, the principle of demonstrating that if a proposition is true for some $k$, then it is also true for $k+1$. So you assume it is true for $k$ and then you demonstrate that, under this assumption, it is also true for $k+1$. So, you show that "if it were true for $k$, then it were also true for $k+1$". And then you merely find some integer $k_0$ for which it is true (maybe none exists - in this case the proposition is not true) ... –  mathse Apr 14 '14 at 20:33

To give you an example of a "failed" induction proof, let $P(k)$ be the proposition $k>k+10$. Now, let's "prove" this by induction.

You assume $P(k)$ holds, i.e., $k>k+10$. Then, adding $1$ on both sides of the inequality gives

$k+1>k+1+10$

which is precisely $P(k+1)$. So now you know that if $P(k)$ is (ever) true, then also $P(k+1)$ is true.

Finally, you check for some base cases: $P(1)$: $1>1+10=11$ is false, $P(2)$: $2>2+10=12$ is false, etc. So $P(k)$ is in fact not true, although $P(k)\implies P(k+1)$ holds.

-
Better express that by showing that from $k > k + 10$ it follows that $k + 1 > k + 1 + 10$. Otherwise an excellent example. –  vonbrand Apr 15 '14 at 3:27
@vonbrand Agreed, I changed it. –  mathse Apr 15 '14 at 9:12