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

  • 1
    Try using the fact that $$\frac{1-x^{n+1}}{1-x} = \sum_{i=0}^{n} x^i.$$2012-12-18
  • 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^n2012-12-18
  • 0
    @AntonioVargas oh thanks! I kind of get the equation now.2012-12-18
  • 0
    Could you change the $1$ in the sum to $i$, please?2012-12-18
  • 1
    @Nur yeah sorry for the typo.2012-12-18
  • 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
    It took me a while to get the whole picture. I understand the equation now. Thanks!2012-12-18
  • 0
    No problem, but you did most of the work anyway lol2012-12-18
  • 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} $.

  • 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$.2012-12-18
  • 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 :)2012-12-18
  • 0
    @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).2012-12-18
  • 0
    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 :)2012-12-18