Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.]

share|improve this question
1  
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
1  
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
1  
@Nur yeah sorry for the typo. –  user38927 Dec 18 '12 at 6:06
show 1 more comment

2 Answers 2

up vote 1 down vote accepted

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

share|improve this 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
add comment

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} $.

share|improve this answer
1  
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.