Consider the case for n = 1:
So the theorem holds for n = 1.
Now assume it holds for some n = N, that is:
We wish to show it holds for n = N + 1 also.
We need to show that this is equal to
There is going to be a way to do this in general, but you should probably start small. Let N = 1, for example. Then we are saying:
The advantage is that we can write this out term by term and see what is happening:
See if you can you use this example and maybe the next few higher values of N to find a way to set up a conditional equation between the two summations.
I'll give you a hint: It's the same pattern as you see when you are proving that