I'm missing something re: proof by induction

[TalkOrigin]

Hi, I'm working through "What is mathematics" by Courant, and in the first chapter he covers proof by mathematical induction. I understand the method, and I do understand the general principle, but I think I'm confused somewhere.

Basically, you have to prove something on the LHS is equal to something on the RHS by induction. So you first show that it's true for a base case (ie n=1) then generalise this to n=k, and then you assume that the equation holds at n=k. Then the next thing to do is that you show that the equation still holds for n=k+1, and so you either add the term to both sides or you multiply both sides by whatever term it is. This is the bit that confuses me, because I think all you have to do is show that now the LHS still equals the RHS, but of course it does, if you take 2 equal things and multiply them by the same number, then of course they will still be equal? I think maybe where I'm going wrong is that, the end result on the RHS will look the same as the RHS for n=k, except it will be k+1 and this shows that it's true. But it don't really get this, I'm not sure why it is that you can't just assume it's going to be true for n=k+1?

I know there's something obvious that I'm not seeing, I just can't get there.

Thanks

 

[Mentallic]

Hi, I'm working through "What is mathematics" by Courant, and in the first chapter he covers proof by mathematical induction. I understand the method, and I do understand the general principle, but I think I'm confused somewhere.

Basically, you have to prove something on the LHS is equal to something on the RHS by induction. So you first show that it's true for a base case (ie n=1) then generalise this to n=k, and then you assume that the equation holds at n=k. Then the next thing to do is that you show that the equation still holds for n=k+1, and so you either add the term to both sides or you multiply both sides by whatever term it is. This is the bit that confuses me, because I think all you have to do is show that now the LHS still equals the RHS, but of course it does, if you take 2 equal things and multiply them by the same number, then of course they will still be equal? I think maybe where I'm going wrong is that, the end result on the RHS will look the same as the RHS for n=k, except it will be k+1 and this shows that it's true. But it don't really get this, I'm not sure why it is that you can't just assume it's going to be true for n=k+1?

I know there's something obvious that I'm not seeing, I just can't get there.

Thanks

We don't know if it's true, which is why we're trying to prove it. If you can show that LHS=RHS for n=k+1 then by induction, your equation to begin with must've been true. If you can show that it isn't equal, then the original equation mustn't be true.

Take for example the sum of the first n terms

$$1+2+...+n=\frac{n(n+1)}{2}$$

When we assume this for n=k, we have the assumption that the following is true

$$1+2+...+k = \frac{k(k+1)}{2}$$

But now to prove it for n=k+1

$$1+2+...+k+(k+1)=\frac{(k+1)((k+1)+1)}{2}=\frac{(k+1)(k+2)}{2}$$

We aren't sure if this is correct, so we go about replacing $1+2+...+k$ on the LHS with $\frac{k(k+1)}{2}$ by our assumption, and then we use algebra to manipulate both sides into becoming the same. If we can do that using valid rules, then the original formula is true for all $n\geq 1$.

Now consider if I instead asked you to prove

$$1+2+...+n = \frac{n(n+2)}{3}$$

It will be valid for your base case n=1, and then you have your assumption, but clearly it's not correct since we know what the right formula is, hence the only way induction will tell us this is when we try and prove it for n=k+1 and we end up with 1=0 or some other nonsense of the sort.

 

[TalkOrigin]

Ahh ok, thanks so much for the thorough explanation! I think I was doing a few things wrong, one of them being that I thought when using n=k+1, if it's a sequence like $a+ar+...+ar^k$ etc, that you just add $$ar^{k+1}$$ on both sides. Actually, you add it on to the left, and say that if the equation is true, then you should be able to substitute k for k+1 on the RHS and it should come out equal. Your example at the end (the incorrect equation) helped a lot. I also didn't realize that of course, IF it is true for any value k, it's obviously true for k+1.

Thanks again

 

[Mentallic]

Ahh I understand what your problem was now.

If you have a series of the form

$$a_1+a_2+...+a_n=f(n)$$

then you assume

$$a_1+a_2+...+a_k=f(k)$$

and solve

$$a_1+a_2+...+a_k+a_{k+1}=f(k+1)$$

which then after applying the assumption, you have

$$f(k)+a_{k+1}=f(k+1)$$

What you were doing instead was

$$a_1+a_2+...+a_k+a_{k+1}=f(k)+a_{k+1}$$

which is true always, as you were saying (taking your assumption to be true).

 

[TalkOrigin]

Yes, exactly! ok so at least I understand this much now, but when you have a series where it's multiplied and not added, for example $(1 + q)(1 + q^2)(1 + q4) ... (1 + q^{(2^k)}) = \frac{1-q^{2^{k+1}}}{1-q}$ does it change (by "it" i mean the method)?

I asked about how to prove this in the h/w section, and it was suggested that I multiply both sides of the equation by $1+q^{2^{k+2}}$ and show that this result is equivalent to $(1 + q)(1 + q^2)(1 + q4) ... (1 + q^{2^k})(1 + q^{2^{k+1}}) = \frac{1-q^{2^{k+2}}}{1-q}$ .

Can i also think of it in this way: that I multiply the LHS by $1+q^{2^{k+2}}$ and it should give the result $\frac{1-q^{2^{k+2}}}{1-q}$ and if this is the result, then the equation is true for n=k?

 

[Vanadium 50]

I think it's helpful to think of it in the other direction.

The first thing you prove is that IF it is true for one n, it is also true for n+1. That's a big if, because it might not be true.
The second thing you prove is that it is true for n=1.

 

[micromass]

So let me explain the intuition behind a proof by induction a bit. Let's pick an easy example:

$$e^{a_1 + ... + a_n} = e^{a_1} ... e^{a_n}$$

This might be obvious to you, but let's try to prove it. First note that for $n=1$, the result is trivial and for $n=2$, we have the usual exponential law $e^{x+y} = e^x e^y$. So what about $n=3$? Well, we have
$$e^{a_1 + a_2 + a_3} = e^{a_1 + a_2} e^{a_3} = e^{a_1} e^{a_2} e^{a_3}$$
where in both cases we have applied the usual exponential law. Now for $n=4$:
$$e^{a_1 + a_2 + a_3 + a_4} = e^{a_1+a_2 + a_3}e^{a_4} = e^{a_1}e^{a_2}e^{a_3}e^{a_4}$$
where in the first equality, we have applied the usual exponential law, and the second equality is the equality for $n=3$. Then for $n=5$:
$$e^{a_1 + a_2 + a_3 + a_4+a_5} = e^{a_1+a_2 + a_3+a_4}e^{a_5} = e^{a_1}e^{a_2}e^{a_3}e^{a_4}e^{a_5}$$
where we have applied the usual exponential law in the first equality, and then the case $n=4$ which we have already proven.

We can obviously continue this process indefinitely, we can do this for $n=6$, $n=7$ and so on by almost copying the previous cases. This suggest a general method which is exactly proof by induction. Proof by induction is just the abstraction of the individual cases. It gives you a method to prove the case $n+1$ from case $n$. You can then find an explicit proof of case $n=66$ (for example), by doing the proof for case $1$, case $2$, case $3$, etc. up to case $66$. So a proof by induction is a general method on how to construct proofs for specific integers.

This suggests how to actually find proofs by induction. The idea is to first prove the case $n=1$, then $n=2$, then $n=3$ and so on until you find a general pattern. The proof by induction then simply abstracts this pattern.

Finally, a word of warning on the dangers of a proof by induction. A proof by induction of course is a rigorous proof and it shows a formula to be correct. But it often givs no information on how to obtain the formula to begin with. For example, consider
$$1 + 2 + 3 + ... + n = \frac{1}{2} n(n+1)$$
This can be easily proved by induction, but that only shows that the formula is correct, but doesn't say how we can find this formula. Knowing how to find a formula is important, because it might give information on how to obtain similar formulas. A proof by induction does not give you such information, it just shows that it is correct. On the other hand, you can consider the following proof of the formula by writing the terms under each other:
$$\begin{array}{ccccccccc} 1 & + & 2 & + & 3 & + & ... & + & n\\ n & + & (n-1) & + & (n-2) & + & ... & + & 1 \end{array}$$
We now notice that the numbers written in columns all add up to $n+1$. So we get that
$$(1 + 2 + 3 + ... + n) + (n + (n-1) + (n-2) + ... + 1) = (n+1) + (n+1) + ... + (n+1) = n(n+1)$$
which gives us the formula immediately. I find this proof way more illuminating by a proof by induction. And it suggests how to find similar proofs. For example, can you find a general formula for the sum of even numbers, or odd numbers this way? The proof by induction gave no such information, but this proof does. This is why mathematicians, while acknowledging that proof by induction is valid, do not always like the proof by induction very much.

 

[Fredrik]

Can i also think of it in this way: that I multiply the LHS by $1+q^{2^{k+2}}$ and it should give the result $\frac{1-q^{2^{k+2}}}{1-q}$ and if this is the result, then the equation is true for n=k?

I answered this in the homework thread. https://www.physicsforums.com/threa...-geometrical-progression.819697/#post-5145970

 

[TalkOrigin]

So let me explain the intuition behind a proof by induction a bit. Let's pick an easy example:

$$e^{a_1 + ... + a_n} = e^{a_1} ... e^{a_n}$$

This might be obvious to you, but let's try to prove it. First note that for $n=1$, the result is trivial and for $n=2$, we have the usual exponential law $e^{x+y} = e^x e^y$. So what about $n=3$? Well, we have
$$e^{a_1 + a_2 + a_3} = e^{a_1 + a_2} e^{a_3} = e^{a_1} e^{a_2} e^{a_3}$$
where in both cases we have applied the usual exponential law. Now for $n=4$:
$$e^{a_1 + a_2 + a_3 + a_4} = e^{a_1+a_2 + a_3}e^{a_4} = e^{a_1}e^{a_2}e^{a_3}e^{a_4}$$
where in the first equality, we have applied the usual exponential law, and the second equality is the equality for $n=3$. Then for $n=5$:
$$e^{a_1 + a_2 + a_3 + a_4+a_5} = e^{a_1+a_2 + a_3+a_4}e^{a_5} = e^{a_1}e^{a_2}e^{a_3}e^{a_4}e^{a_5}$$
where we have applied the usual exponential law in the first equality, and then the case $n=4$ which we have already proven.

We can obviously continue this process indefinitely, we can do this for $n=6$, $n=7$ and so on by almost copying the previous cases. This suggest a general method which is exactly proof by induction. Proof by induction is just the abstraction of the individual cases. It gives you a method to prove the case $n+1$ from case $n$. You can then find an explicit proof of case $n=66$ (for example), by doing the proof for case $1$, case $2$, case $3$, etc. up to case $66$. So a proof by induction is a general method on how to construct proofs for specific integers.

This suggests how to actually find proofs by induction. The idea is to first prove the case $n=1$, then $n=2$, then $n=3$ and so on until you find a general pattern. The proof by induction then simply abstracts this pattern.

Finally, a word of warning on the dangers of a proof by induction. A proof by induction of course is a rigorous proof and it shows a formula to be correct. But it often givs no information on how to obtain the formula to begin with. For example, consider
$$1 + 2 + 3 + ... + n = \frac{1}{2} n(n+1)$$
This can be easily proved by induction, but that only shows that the formula is correct, but doesn't say how we can find this formula. Knowing how to find a formula is important, because it might give information on how to obtain similar formulas. A proof by induction does not give you such information, it just shows that it is correct. On the other hand, you can consider the following proof of the formula by writing the terms under each other:
$$\begin{array}{ccccccccc} 1 & + & 2 & + & 3 & + & ... & + & n\\ n & + & (n-1) & + & (n-2) & + & ... & + & 1 \end{array}$$
We now notice that the numbers written in columns all add up to $n+1$. So we get that
$$(1 + 2 + 3 + ... + n) + (n + (n-1) + (n-2) + ... + 1) = (n+1) + (n+1) + ... + (n+1) = n(n+1)$$
which gives us the formula immediately. I find this proof way more illuminating by a proof by induction. And it suggests how to find similar proofs. For example, can you find a general formula for the sum of even numbers, or odd numbers this way? The proof by induction gave no such information, but this proof does. This is why mathematicians, while acknowledging that proof by induction is valid, do not always like the proof by induction very much.

This was a great post, thank you.