# Understanding $\frac {b^{n+1}-a^{n+1}}{b-a} = \sum_{i=0}^{n}a^ib^{n-i}$

I'm going through a book about algorithms and I encounter this.

$$\frac {b^{n+1}-a^{n+1}}{b-a} = \sum_{i=0}^{n}a^ib^{n-i}$$

How is this equation formed? If a theorem has been applied, what theorem is it?

[Pardon me for asking such a simple question. I'm not very good at maths.]

-
Try using the fact that $$\frac{1-x^{n+1}}{1-x} = \sum_{i=0}^{n} x^i.$$ –  Antonio Vargas Dec 18 '12 at 5:20
@AntonioVargas oh thanks! I kind of get the equation now. –  user38927 Dec 18 '12 at 5:24
The proof of that is just as hard as the proof of his statement, you just substitute a/b=x, and multiply both sides by b^n –  Ethan Dec 18 '12 at 5:24
Could you change the $1$ in the sum to $i$, please? –  NeverBeenHere Dec 18 '12 at 6:01
@Nur yeah sorry for the typo. –  user38927 Dec 18 '12 at 6:06

Multiply both sides by b-a, watch for the cancling of terms, and you will have your answer.

-
It took me a while to get the whole picture. I understand the equation now. Thanks! –  user38927 Dec 18 '12 at 5:38
No problem, but you did most of the work anyway lol –  Ethan Dec 18 '12 at 5:39
hahas maths is fun :D –  user38927 Dec 18 '12 at 5:44

Send $i \mapsto i-1$ then $\displaystyle f(n) = \sum_{i=0}^{n}a^{i}b^{n-i} = \sum_{i=1}^{n+1}a^{i-1}b^{n-i+1}\implies a f(n) = b\sum_{i=1}^{n+1}a^{i}b^{n-i}$

$\displaystyle \implies af(n) = -b^{n+1}+a^{n+1}+b\sum_{i=0}^{n}a^{i}b^{n-i} =-b^{n+1}+a^{n+1}+bf(n)$ and rearranging:

$\displaystyle bf(n)-af(n) = b^{n+1}-a^{n+1} \implies (b-a)f(n) = b^{n+1}-a^{n+1} \implies f(n) = \frac{b^{n+1}-a^{n+1}}{b-a}$.

-
I should probably mention that sending $i \mapsto i-1$ is the same as subbing $i = k-1$ -- that's $k = i+1$. When $i = 0, ~ k = 1$ and when $i = n, ~ k = n+1$. So we have $\sum_{k=1}^{n+1}\cdots$ But $k$ is a dummy variable and we can replace it with anything. For convenience replace it back with $i$. So we have $\sum_{i=1}^{n+1}\cdots$. –  NeverBeenHere Dec 18 '12 at 6:28
thanks so much for everything! Actually I've done fundamentally the same thing as this but I didn't send i↦i-1 and write it down in the mathematician way, I simply multiplied both side by b-a [as Ethan told me] and got $$b^{n+1}-a^{n+1}=\sum_{i=0}^{n}a^{i}b^{n-i+1}-\sum_{i=0}^{n}a^{i+1}b^{n-i}$$ Then I expanded $$\sum_{i=0}^{n}a^{i}b^{n-i+1}-\sum_{i=0}^{n}a^{i+1}b^{n-i}$$ and got $$(b^{n+1}+ab^n+a^2b^{n-1}...)-(ab^n+a^2b^{n-1}...+a^{n+1})$$ In which I spotted the $$b^{n+1}-a^{n+1}$$ and realised I could just cancel everything else -- that's when I gained a full understanding of the equation :) –  user38927 Dec 18 '12 at 7:10
@Arch Cool! I'm a dictator so I would like to keep everything under control -- the big sigma is my prison gates! :] (Even when telescoping something, I never write the terms out -- rather, I map one of the indexes to the other and it cancels out -- it's just an old habit of mine). –  NeverBeenHere Dec 18 '12 at 7:23
hahas that is definitely better than writing everything out which is really time-consuming! But I have not yet gotten used to being in the prison of sigma gates. I shall try being in the prison more often and make it a habit :) –  user38927 Dec 18 '12 at 7:35