Prove $u_n$ = $n$ $*$ $2^n$ with mathematical induction

Question

I need to prove that

$u_n$ = $n \times 2^n$

using mathematical induction with the below information.

$u_1\;=\;2\;\text{ and }\;\;u_{n+1}=2\left(u_n+\frac{u_n}n\right)\;\text{ for }\;n\geq1$

I have expanded the first few terms such that

$u_1\;=\;2$

$u_2\;=\;8$

$u_3\;=\;24$

$u_4\;=\;64$

$u_5\;=\;160$

I have also proved that $P(1)$ is true such that $u_n$ = $2$.

Therefore, $u_k$ = $k \times 2^k$ .

How do i prove the case for $k+1$ ?

Answer 1

We need to prove $ \forall n \geq 1,P(n) \implies P(n+1)$

Base case: $$u_2=2\cdot2^2=8=2(u_1+\frac{u_1}{1})=2(2+2)=2*4=8$$

Assume that it is true for $n=k$

thus $$u_k=k\cdot2^k$$

Now you have to prove it for $n=k+1$

use $$\;\;u_{n+1}=2\left(u_n+\frac{u_n}n\right)\;for\;n\geq1$$ $$u_{k+1}=2\left(u_k+\frac{u_k}k\right)$$

but we have $$u_k=k\cdot2^k$$ put back into the equation above we get

$$u_{k+1}=2\left(k\cdot2^k+2^k\right)=(k+1)\cdot2^{k+1}$$

Answer 2

Let's substitute $u_k$ into your recursive formula:$$u_{k+1}=2(u_k+\frac{u_k}k)=2(k\cdot2^k+\frac{k\cdot2^k}k)=2\cdot2^k\cdot(k+1)=(k+1)\cdot2^{k+1}$$So we are done with the induction step

Answer 3

You need to prove that $\forall n \geq 1$ $P(n) \implies P(n+1)$.

Let $n \geq 1$. If $P(n)$ is true then $u_n= n \cdot 2^n$.

So: $$u_{n+1}=2 \left(u_n+\frac{u_n}{n} \right)=2\left( n 2^n +\frac{n 2^n}{n} \right)=2 (n+1) 2^n=(n+1)2^{n+1}$$ i.e $P(n+1)$ is true.

Answer 4

Hint: $$u_{k+1}=2(u_k+\frac{u_k}{k})=2(k2^k+\frac{k2^k}{k})=…$$

Answer 5

For the induction step we need to prove that

$$u_k=k\,2^k\implies u_{k+1}=(k+1)2^{k+1}$$

then consider

$$u_{k+1}\stackrel{by\,Def.}=2\left(u_{k}+\frac{u_{k}}{k}\right)=2\,u_k\,\frac{k+1}{k}\stackrel{Ind. Hyp.}=2\,k\,2^k\,\frac{k+1}{k}=(k+1)\,2^{k+1}$$