1
$\begingroup$

I am interested in solving the recurrence relation using iterative method. I know how to solve it using generating function and another method using solution of associated linear homogeneous recurrence relation and particular solution described in Rosen's Discrete Math book. I came up with some summation (below) but I don't know how to find its closed form. I checked WolframAlpha and it provided me with this $$\sum_{k=0}^{n}k\cdot2^{n-k}=-n+2^{n+1}-2$$ How to show this?

$\endgroup$

6 Answers 6

6
$\begingroup$

HINT:

$$\sum_{k=0}^nk2^{n-k}=2^n\sum_{k=0}^nk\left(\frac12\right)^k\;,$$

so you’re done if you can evaluate

$$f(x)=\sum_{k=0}^nkx^k$$

at $x=\frac12$. Start with $g(x)=\sum_{k=0}^nx^k$, differentiate, and multiply by $x$. (I’m assuming that you know a closed form for $g(x)$.)

$\endgroup$
2
  • $\begingroup$ Is $g(x)$ supposed to be $\sum_{k=0}^{n} x^k$? $\endgroup$
    – gg1
    Nov 30, 2015 at 12:31
  • $\begingroup$ @gggg: It is indeed; thanks for catching that. $\endgroup$ Nov 30, 2015 at 12:32
3
$\begingroup$

By induction:

$$S_{n+1}=2S_n+n+1,$$ as all terms are multiplied by $2^{n+1-k}$ instead of $2^{n-k}$, and there is an extra term $(n+1)\cdot2^{n-n}$.

On the other hand,

$$-(n+1)+2^{(n+1)+1}-2=2(-n+2^{n+1}-2)+n+1.$$

The base case $n=0$ is also verified:

$$\sum_{k=0}^{0}k\cdot2^{n-k}=0=-0+2^{0+1}-2.$$

$\endgroup$
2
  • $\begingroup$ This is interesting but I don't know where did you get the right hand side of the first equation. $\endgroup$
    – gg1
    Nov 30, 2015 at 13:03
  • $\begingroup$ @gggg: this is explained by the sentence that follows! $\endgroup$
    – user65203
    Nov 30, 2015 at 13:32
2
$\begingroup$

Semi-graphically:

$$1\cdot16+2\cdot8+3\cdot4+4\cdot2+5\cdot1\\=\\ \begin{align} 16+8+4+2+1+&&\to&&{32-1}+\\ 8+4+2+1+&&\to&&{16-1}+\\ 4+2+1+&&\to&&{8-1}+\\ 2+1+&&\to&&{4-1}+\\ 1\ \ \ &&\to&&{2-1}+\\ &&\to&&{1-1}\ \ \ \end{align}\\ =\\(64-1)-6.$$

Then general pattern is $(2^{n+1}-1)-(n+1)$.

Graphically:

enter image description here

$\endgroup$
1
  • $\begingroup$ Beautiful explanation. +1 $\endgroup$
    – user284001
    Dec 3, 2015 at 14:24
1
$\begingroup$

First, once you have a candidate for the closed form, you can prove that it works using induction. Regarding your sum, note that is has the form

$$ c \sum_{k=0}^n k x^{k - 1} = c \left( \sum_{k=0}^n x^k \right)' = c \left( \frac{x^{n+1} - 1}{x - 1} \right)'. $$

Indeed, $c = 2^{n-1}$ and $x = \frac{1}{2}$.

$\endgroup$
0
$\begingroup$

You can see it as \begin{align} \sum_{k=0}^n k2^{n-k} = {} & 2^{n} \sum_{k=1}^n k2^{-k} \\ & \text{letting $x=\frac12$,} \\ = {} & \frac{1}{x^n} \sum_{k=1}^n kx^k = \frac{1}{x^{n-1}} \sum_{k=1}^n kx^{k-1} \end{align} We further divided by $x$ in the last equality so that $kx^{k-1}$ is exactly the derivative of $x^k$, which then makes it possible to get rid of the multiplying factor $k$ in each term $kx^k$ term. Indeed, let $$ F(x) = \sum_{k=1}^n kx^{k-1} $$ so that what you are looking for is $2^{n-1}F(1/2)$.

Now, as observed, $$ F'(x) = \sum_{k=1}^n x^k = \frac{1-x^{n+1}}{1-x} - 1 $$ where the $-1$ comes from the fact that we are summing from $k=1$ and not $k=0$. Now it's just a matter of integrating...

$\endgroup$
-1
$\begingroup$

From $$ \sum_{k=0}^{n}x^{k}=\frac{1-x^{n+1}}{1-x}$$ differentiate to get$$ \sum_{k=0}^{n}kx^{k-1}=\frac{-nx^{n}\left(1-x\right)+1-x^{n}}{\left(1-x\right)^{2}}$$ Multiplying by $x$ so that $$ \sum_{k=0}^{n}kx^{k}=x\cdot\frac{-nx^{n}\left(1-x\right)+1-x^{n}}{\left(1-x\right)^{2}}$$ and replace $x$ by $\frac{1}{2}$, we get$$ \sum_{k=0}^{n}k\left(\frac{1}{2}\right)^{k}=-n2^{-n}+2-2^{-n+1}$$ Lastly, by multiplying $2^{n}$, $$ \sum_{k=0}^{n}k2^{n-k}=-n+2^{n+1}-2$$

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