7
$\begingroup$

I just watched a tutorial on recurrence by substitution. In the tutorial, it mentioned about rewriting

$\sum\limits_{i=1}^\mathbb{k}{2^i}$

as (2k+1 - 2). My question is can I generalize it as xlimit + 1 - x where x is the base.

$\endgroup$

3 Answers 3

14
$\begingroup$

Let $S = \sum_{i=1}^k x^i$. Consider the following manipulation $$S = x + x^2 + x^3 + \cdots + x^k = x(1 + x + \cdots + x^{k-1}) = x(S + 1 - x^k)$$ It follows that $S = (x^{k+1} - x)/(x - 1)$

$\endgroup$
6
$\begingroup$

Nice observation and almost true: $$ \sum\limits_{i=1}^\mathbb{n}{a^i} = \frac{a^{n+1}-a}{a-1} $$ It's a special case of a geometric progression.

$\endgroup$
1
  • 1
    $\begingroup$ As an example, $\sum_{i=1}^5 10^i=\frac{10^6-10}9$, which the OP should verify by evaluating each side. $\endgroup$ Nov 4, 2015 at 12:23
0
$\begingroup$

Let $$a(n)=b^n$$ for some $b$; then $$\Delta a(n)=a(n+1)-a(n)=b^{n+1}-b^n=b^n(b-1);$$ divide both sides by $b-1$: $$b^n=\frac{\Delta a(n)}{b-1};$$ substitute back for $a(n)$: $$a(n)=b^n=\frac{\Delta (b^n)}{b-1}={\large\Delta}\left(\frac{b^n}{b-1}\right).$$ Evaluate $$\sum\limits_{k=1}^na(k).$$ Apply the fundamental theorem of discrete calculus: $$\sum\limits_{k=1}^na(k)=\bigg({\large\Delta}^{-1}a(k)\bigg)\Bigg|_{k=1}^{n+1}=\left(\frac{b^k}{b-1}\right)\Bigg|_{k=1}^{n+1}=\frac{b^{k+1}}{b-1}-\frac{b}{b-1};$$ write out the answer: $$\therefore\sum\limits_{k=1}^nb^k=\frac{b^{k+1}-b}{b-1}.$$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.