0

I'm trying to prove this by mathematical induction, but I just can't seem to get the answer that I should be getting. Here's what I have so far:

Let $P(n)$ be the statement (this is the equation that I'm supposed to prove by induction): $$\sum_{i=0}^n (n-i)2^i = 2^{n+1}-n-2,$$ Basis step: $(n=0)$: $$P(0) = (0-0)2^0 = 2^{0+1}-0-2 = 0 = 0.$$ Inductive step: Assume that $P(n)$ is true, that is, $$\sum_{i=0}^n (n-i)2^i = 2^{n+1}-n-2.$$

Showing that $P(n+1)$ is also true, that is: $$\sum_{i=0}^{n+1} (n-i)2^i = 2^{n+2}-(n+1)-2 $$ $$ = 2^{n+2}-n-3 $$ $P(n+1) ={}$ $$\sum_{i=0}^{n+1} (n-i)2^i + n-(n+1)2^{n+1}$$ $$ = 2^{n+1}-n-2+(n-n-1)2^{n+1} $$ $$ = 2^{n+1}-n-2-(1)2^{n+1}$$

As can be seen, I am not getting back the result I'm supposed to be getting for $P(n+1)$. Can someone assist me here, please?

Tianlalu
  • 5,177
pythonprogrammer12
  • 3

2 Answers2

3

Your $P(n+1)$ is missing a $+1$ (as in, for "$n+1$") inside the sum parenthesis.

Hint: \begin{align} \sum_{i=0}^{n+1} (n+1-i)2^i &=\sum_{i=0}^{n+1} (n-i)2^i +\sum_{i=0}^{n+1}2^i \\ &=(n-(n+1))2^{n+1} +\color{blue}{\sum_{i=0}^{n} (n-i)2^i} +\sum_{i=0}^{n+1}2^i \\ \end{align} Now you can use $\color{blue}{P(n)}$. Also, you need $\displaystyle \sum_{i=0}^{n+1} 2^i = 2^{n+2} -1$.

Rócherz
  • 3,976
  • (+1) What great use of colour! – Shaun Nov 23 '18 at 04:59
  • Hmm, I'm not quite understanding why there are 3 terms in the equation for P(n+1). I thought that we're supposed to go up to P(n) then substitute (n+1) for n in the next term in the sequence? – pythonprogrammer12 Nov 23 '18 at 06:21
  • Look at your $\color{blue}{P(n)}$: you have $\color{blue}{\displaystyle\sum_{i=0}^n (n-i)2^i}$ on the left-hand side. For $P(n+1)$, you would have $$\sum_{i=0}^{n+1} ((n+1)-i)2^i =\color{blue}{\sum_{i=0}^n ((n\bbox[yellow]{+1})-i)2^i} +((n+1)-(n+1))2^{n+1}$$ on the left-hand side, but you can't just use $\color{blue}{P(n)}$ there, because of the $\bbox[yellow]{+1}$. You have to take that $\bbox[yellow]{+1}$ out of the sum for it to resemble that of $\color{blue}{P(n)}$. – Rócherz Nov 23 '18 at 08:06
1

Given $$P(\color{red}n)=\sum_{i=0}^\color{red}n (\color{red}n-i)2^i,$$ note: $$\begin{align}P(\color{red}0)=&\sum_{i=0}^\color{red}0 (\color{red}0-i)2^i = (\color{red}0-0)2^0=0=2^{\color{red}0+1}-\color{red}0-2; \ \ \text{(base step)}\\ P(\color{red}1)=&\sum_{i=0}^\color{red}1 (\color{red}1-i)2^i = (\color{red}1-0)2^0+(\color{red}1-1)2^1=1;\\ \vdots\\ P(\color{red}{n})=&\sum_{i=0}^{\color{red}{n}} (\color{red}{n}-i)2^i=\color{blue}{2^{n+1}-n-2}; \ \ \text{(inductive hypothesis)}\\ P(\color{red}{n+1})=&\sum_{i=0}^{\color{red}{n+1}} (\color{red}{n+1}-i)2^i =\\ =&\sum_{i=0}^n (n+1-i)2^i+\require{cancel} \cancel{(n+1-(\color{red}{n+1}))2^{n+1}}=\\ =&\sum_{i=0}^n(n-i)2^i+\sum_{i=0}^n2^i=\\ =&\color{blue}{2^{n+1}-n-2}+2^{n+1}-1=\\ =&2^{n+2}-(n+1)-2.\end{align}$$

farruhota
  • 31,482