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.
3 Answers
$\begingroup$
$\endgroup$
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)$
answered Nov 4, 2015 at 11:23
$\begingroup$
$\endgroup$
1
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.
-
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
$\begingroup$
$\endgroup$
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}.$$
