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

  • 0
    @Arch that's alright! I tried to fix it myself but it told me that I've no enough rep or something to that effect! :[2012-12-18

2 Answers 2

1

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

  • 0
    hahas maths is fun :D2012-12-18
1

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

  • 0
    hahas that is definitel$y$ 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 :)2012-12-18