1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Try using the fact that $$\frac{1-x^{n+1}}{1-x} = \sum_{i=0}^{n} x^i.$$ $\endgroup$ – Antonio Vargas Dec 18 '12 at 5:20
  • $\begingroup$ @AntonioVargas oh thanks! I kind of get the equation now. $\endgroup$ – user38927 Dec 18 '12 at 5:24
  • 1
    $\begingroup$ 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 $\endgroup$ – Ethan Dec 18 '12 at 5:24
  • $\begingroup$ Could you change the $1$ in the sum to $i$, please? $\endgroup$ – NeverBeenHere Dec 18 '12 at 6:01
  • 1
    $\begingroup$ @Nur yeah sorry for the typo. $\endgroup$ – user38927 Dec 18 '12 at 6:06
1
$\begingroup$

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

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

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – NeverBeenHere Dec 18 '12 at 6:28
  • 1
    $\begingroup$ 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 :) $\endgroup$ – user38927 Dec 18 '12 at 7:10
  • $\begingroup$ @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). $\endgroup$ – NeverBeenHere Dec 18 '12 at 7:23
  • $\begingroup$ 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 :) $\endgroup$ – user38927 Dec 18 '12 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy