3

I have the sequence:
$$ \begin{cases} a_0=1 \newline a_n = 2a_{n-1}+1, n \ge 1 \end{cases}$$

And I want to prove that $a_n = 2^{n+1}-1$ for all whole number $n \ge 0$
I started by calculating $a_0,a_1,a_2$ and $a_3$:
$a_0=2^{0+1}-1=0$
$a_1=2^{1+1}-1=3$
$a_2=2^{2+1}-1=7$
$a_3=2^{3+1}-1=15$

If I have understood this procedure correctly, I now need to assume $n=p$, which gives: $a_p=2^{p+1}-1=2\times2^p-1$
Now I need to prove that this is true for the next number: $p+1$ gives $2^{(p+1)+1}-1=2^{2+p}-1=2^2 \times 2^p-1$
Now it's time to use: $a_n = 2a_{n-1}+1$
$a_p = 2a_{p-1}+1$
Since this $2a_{p-1}$ includes $p-1$ and not just $p$ I don't really know how to continue. Can someone explain?

Firellsp
  • 117
  • 1
    You can easily prove it by induction. For $n=1$ your hypothesis is true, for $n>1$ we get $a_n=2a_{n-1}+1=2\cdot (2^n-1) +1$ – Jochen Sep 27 '22 at 16:22
  • 2
    The induction step is $$a_{n+1}=2a_n+1=(2^{n+2}-2)+1=2^{n+2}-1$$ finishing the proof. – Peter Sep 27 '22 at 16:22

0 Answers0