Proof by Induction: Proving the Sum of Squares Identity

[fluppocinonys]

1.

2.

3.

 

[CompuChip]

For the first one I suggest a proof by induction.
It's easy to check that the direct formula holds for the case n = 1. Now suppose that for all k \le n, it is true that
u_k = 3 \left( \frac{1}{5} \right)^n - 1.
Then use the recursive definition to show that
u_{n + 1} = 3 \left( \frac{1}{5} \right)^{n + 1} - 1.For 2: What is r^3 - (r - 1)^3 ?

Let's start with those two, shall we?

 

[statdad]

Just a note:

<br /> \sum_{r=1}^n r^3 = \left[\frac{n(n+1)^2} 2\right]<br />

is not correct, so trying to do the second portion with this won't work. You should have

<br /> \sum_{r=1}^n r^3 = \left[\frac{n(n+1)}2\right]^2<br />

 

[fluppocinonys]

Thanks for the replies, I have a typo error on Question 2, which should be
{\left[ {\frac{{n\left( {n + 1} \right)}}{2}} \right]^2} , thanks for correcting me.

Here are my attempts,

But I don't quite understand your explanation on qn 1...

 

[CompuChip]

Can you write down that "proof" a bit more clearly? Because I have no idea what it is you were doing there.

For the first one, I suggested a proof by induction. Have you seen that technique before?

 

[fluppocinonys]

Can you write down that "proof" a bit more clearly? Because I have no idea what it is you were doing there.

For the first one, I suggested a proof by induction. Have you seen that technique before?

Which proof are you referring to? My attempts on question 2?
And I've not seen that technique before, please guide me thanks.

 

[CompuChip]

Ah, never mind, I wasn't quite awake reading your post. I was indeed referring to your attempt on question 2, but now that I've read it a second time it makes sense.

Proof by induction is a very powerful proof technique that you should learn sooner or later. So it might as well be now. The idea is as follows.
You have some statement which contains one integer variable, n. First you show that the statement is true for some low n, like n = 0 or n = 1. Then you do the induction step: you assume that it is true for all values less than or equal to n and then you show that it must be true for n + 1.

Let me first give you an example.
Statement:

\sum_{r = 1}^n r = \frac12 n (n + 1)​

Proof:
Part I (the base case). First we check the statement for n = 1. On the left hand side, we have the sum from r = 1 to 1 over r, which is 1. On the right hand side, we get 1/2 * 1 * 2 = 1. So it's true. If you want you can also cover some more cases n = 2, 3, ... although n = 1 is enough.

Part II: (The induction step). Let's assume that the statement is true, for all k less than or equal to some specific and fixed n. This is called the induction hypothesis. We must show that it is then also true for n + 1. Well, splitting off the last term,
\sum_{r = 1}^{n + 1} r = (n + 1) + \sum_{r = 1}^n r \stackrel{\text{I.H.}}{=} (n + 1) + \frac12 n (n + 1) = \frac12 (n + 1) (n + 2).
Note the equality marked with "I.H." - there I have used the induction hypothesis for k = n.

Explanation: The proof is finished. Now why have we proven the statement? Let's see: we have checked that it is true for n = 1 by hand, so it holds for n = 1. We have shown in the second part of the proof, that if it holds for n = 1, then it also holds for n = 2. Since it does hold for n = 1, it holds for n = 2. We have shown that if it holds for n = 1 and n = 2, which it does, then it holds for n = 3. So it holds for n = 1, 2 and 3. But then it also holds for n = 4. And so on. For every value of n you can apply such a reasoning, showing that by applying the induction step (part II) to the base case (part I) the statement is true.
So, it is true for any value of n like you wanted.

This seems like a strange way of proving something at first (at first sight, it may seem that we are assuming what we want to prove in part II, although this is not true if you look carefully) but it's very useful. So scrutinize my proof again, and if you feel like it, try it on your first question.

Or if you need a test case, you can again try proving the identity for
\sum_{r = 1}^n r^2
from exercise 2, using a proof by induction.