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$
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)$

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$
  • 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$ – Akiva Weinberger Nov 4 '15 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}.$$

| cite | improve this answer | |
$\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.