Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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 at 20:23
    
@NigelOvermars yep, this is also something good to remember! –  Marter Js Apr 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 at 20:33

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
1  
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 at 3:27
    
@vonbrand Agreed, I changed it. –  mathse Apr 15 at 9:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.