Define sum explicitly and proof result with induction

49 Views Asked by At

Define sum explicitly and proof result with induction:

$$ p(n)= \sum_{k=0}^{n}2^k $$

Solution

$$ p(n)= \sum_{k=0}^{n}2^k = 2+4+8+16+32+\dots + 2^k $$

Computing few values of $p(n)$ in order to identify explicit expression for sum.

$p(0) = 1, p(1)=3,p(2)=7,p(3)=15,p(4)=31,p(5)=63$

By looking at these values it is visible that it looks almost like $p(n)=2^n$, except it seems to be off by 1 with every value. Looks like we need to offset $p(n)=2^n$ by one, we get $p(n)=2^n -1$. Computing $p(0)=2^0-1 = 0,p(1)=1,p(2)=3,p(3)=7$ reveals it is not valid expression. Looks like it needs to be adjusted with $n = n +1$ since at the moment $p(1)=p(0),p(2)=p(1),\dots$. We get $\boxed{p(n)=2^{n+1}-1}$

Induction proof

Assume

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

is true when $n \ge o$.

Base case

$$ p(0)=2^{0+1}-1= 1 $$

Induction step

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

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

utilize the fact that

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

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

utilize the fact that (step 1)

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

$$ 2^{n+1}+2^{n+1}= 2^{n+2} $$

$$ 2^{n+2} = 2^{n+2} $$

$$\tag*{$\square$}$$

1

There are 1 best solutions below

0
On

The argument is right. Writing an equality and doing operations on it is not the way to write a proof, though. It is a lot better if you start with what you have, and use your hypotheses to get where you want. Here, using the inductive hypothesis in the second equality,
$$ \sum_{k=0}^{n+1}2^k=2^{n+1}+\sum_{k=0}^n2^k=2^{n+1}+2^{n+1}-1=2\times 2^{n+1}-1=2^{n+2}-1, $$ and the inductive step is completed.