1

$a_n$ = 2$a_{n-1}$ + 1, with the initial conditions $a_0$ = 0, $a_1$ = 1

Apparently the solution is from the Tower of Hanoi problem, but having trouble coming with the this on my own.

Diante
  • 189
  • 1
    You can prove it by induction. Suppose that $a_n=2a_{n-1}+1$ for all $n$ and that $a_k=2^k-1$ for some $k$. Then $a_{k+1}=2a_k+1$ by the recurrence relation and then $2a_k+1=\dots$ by the induction hypothesis which simplifies to... which by the principle of mathematical induction implies... – JMoravitz Apr 10 '17 at 03:56
  • 2
    Hint: write it as $;a_n+1=2(a_{n-1}+1),$. P.S. with the initial conditions That's a first order recurrence, so it only needs one initial condition. – dxiv Apr 10 '17 at 03:57
  • It is very easy just go straight.... – Mayank Deora Apr 10 '17 at 04:09
  • 1
    @Community Not sure I see how this is a duplicate, since the referenced question had asked how to solve while this one was only asking how to prove that a certain form is in fact a solution. The answers may overlap, of course, but that alone doesn't make the question a duplicate. – dxiv Apr 10 '17 at 05:50

0 Answers0