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:
- 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:
- If I
assumethat 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$.
- Ok, so I
assumedthat 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$.
- 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.