You asked two questions in your following up.
In algebra, our expressions always stand for numbers. When we sum numbers, we get a number. I could have, and perhaps should have, used a u-substitution. Let's do the proof that way, starting here:
[MATH]\therefore \dfrac{x^{2^{(n+1)}} - 1}{x + 1} = (x^{2^n} + 1) * \sum_{j=0}^{2^n - 1} (-\ 1)^j x^{(2^n - 1 - j)}.[/MATH]
[MATH]\text {Set } u = \sum_{j=0}^{2^n - 1} (-\ 1)^j x^{(2^n - 1 - j)}.[/MATH]
We have replaced the summation notation with a single variable, but notice that, for what we want to prove, the summands in u have the wrong form (we want 2^(n + 1) rather than 2^n) and the wrong range of summation (we want 0 to 2^(n + 1) - 1 rather than 0 to 2^n - 1). So we still have work to do. But let's proceed with the substitution as a starting point.
[MATH]\therefore \dfrac{x^{2^{(n+1)}} - 1}{x + 1} = (x^{2^n} + 1) * u = (x^{2^n} * u) + u[/MATH].
Nothing complex at all if you remember that that seemingly complex summation is just a number and that you learned the distribution law the first week in algebra. And to figure out what that first product equals, we use the distribution law again. We can work with an arbitrary summand.
[MATH]x^{2^n} * (-\ 1)^j x^{(2^n - 1 - j)} = (-\ 1)^j x^{(2^n + 2^n - 1 - j)} =[/MATH]
[MATH](-\ 1)^j x^{(2 * 2^n - 1 - j)} = (-\ 1)^j x^{(2^{n+1)} - 1 - j)}.[/MATH]
So now we use a second substitution:
[MATH]\text {Set } v = x^2 * u = \sum_{j=0}^{2^n - 1} (-\ 1)^j x^{(2^{(n+1)} - 1 - j)} \implies \dfrac{x^{2^{(n+1)}} - 1}{x + 1} = v + u.[/MATH]
So I hope that addresses your first question. We can see the logic better if we use u and v instead of those two complex summations, but of course u and v can be replaced by the summations at any time. Any concerns remaining?
Notice that, in terms of where we want to get, v expanded has exactly the right expression as a summand, but still has the wrong range of summation, and u is wrong in both respects. Where we are now is:
[MATH]\dfrac{x^{2^{(n+1)} - 1}{x + 1} = x^2u + u = v + u = v + \sum_{j=0}^{2^n - 1} (-\ 1)^j x^{(2^n - 1 - j)}.[/MATH]
Let's start getting the summands in u into the form that we need: we want 2^(n + 1) rather than 2^n. So we pick an arbitrary summand.
[MATH](-\ 1)^j x^{(2^n - 1 - j)} =(-\ 1)^j x^{(2^n + 2^n - 1 - j - 2^n)} = (-\ 1)^j x^{(2 * 2^n - 1 - \{j + 2^n\})} =[/MATH]
[MATH](-\ 1)^j x^{(2^{(n+1)} - 1 - \{j + 2^n\})}.[/MATH]
Great, we have the exponent we want and we can say
[MATH]u = \sum_{j=0}^{2^n - 1} (-\ 1)^j x^{(2^{(n+1)} - 1 - \{j + 2^n\})}.[/MATH]
The summand is closer to what we want, but we want to subtract j rather than (j + 2^n). But, if each summand contains only a linear function of j, we can always adjust that function by making a compensating adjustment to j's limits of summation. Unfortunately, this summand contains both a linear function of j and (-1)^j, which is definitely not linear. Is there anyway to adjust j so that (-1)^j is not affected? Yes, easily.
[MATH]j \text { and } j' \text { both even} \implies (-\ 1)^j = 1 = (-\ 1)j'.[/MATH]
[MATH]j \text { and } j' \text { both odd} \implies (-\ 1)^j = -\ 1 = (-\ 1)j'.[/MATH]
So any transformation that preserves parity is fine. Now let's look at dealing with the linear function in j: we want
[MATH]j + 2^n = j'[/MATH], which preserves parity and substitutes a term with j' for one with j + 2^n. Furthermore,
[MATH]j + 2^n = j' \implies j' = 2^n \text { if } j = 0,\ j'= 2^n + 1 \text { if } j = 1,\ ...\ \text { and }[/MATH]
[MATH]j' = 2^n + 2^n - 1 = 2 * 2^n - 1 = 2^{(n+1)} - 1 \text { if } j = 2^n - 1.[/MATH]
That looks very encouraging because it gets us to the 2^(n+1) - 1 upper bound on summation that we want. In short
[MATH]u = \sum_{j=0}^{2^n - 1} (-\ 1)^j x^{(2^{(n+1)} - 1 - \{j + 2^n\})} = \sum_{j'=2^n}^{2^{(n+1)} - 1} (-\ 1)^{j'} x^{(2^{(n+1)} - 1 - j')}.[/MATH]
So we can drop the prime from the j prime.
[MATH]u = \sum_{j=2^n}^{2^{(n+1)} - 1} (-\ 1)^j x^{(2^{(n+1)} - 1 - j)}.[/MATH]
Now it is just tidying up and eliminating the substitutions
[MATH]\dfrac{x^{2^{(n+1)}} - 1}{x + 1} = v + u \implies[/MATH]
[MATH]\dfrac{x^{2^{(n+1)}} - 1}{x + 1} = \sum_{j=0}^{2^n - 1} (-\ 1)^j x^{(2^{(n+1)} - 1 - j)} + \sum_{j=2^n}^{2^{(n+1)} - 1} (-\ 1)^j x^{(2^{(n+1)} - 1 - j)} \implies[/MATH]
[MATH]\dfrac{x^{2^{(n+1)}} - 1}{x + 1} = \sum_{j=0}^{2^{(n+1)} - 1} (-\ 1)^j x^{(2^{(n+1)} - 1 - j)}.[/MATH]
Lots to learn from this problem though I'd not call it easy.
(1) If you do not see an inductive proof right away, run some low numbers and see if that gives you clues as to why the proposition is true.
(2) Utilize substitution of variables to avoid long cumbersome expressions and the errors that come with them.
(3) Learn how to manipulate indices.
PS I apologize for any typos. I have tried to find them, but my eyes and brain are getting tired.
