Define recursively b sub 0 = 1 and for n > 0, let b sub n = 3b sub (n−1) − 1. Prove by induction the formula holds: b sub n =(3^(n)+1)/2.
I started out with a basis: Let n=1 We get that 2=2
Induction Step: Assume for a fixed n, n>0, that 3b sub (n-1) -1 = (3^(n)+1)/2 Want to show that if the formula is true for n, it works for n+1.
Where should I go from here? I am not all too familiar with induction proofs involving recursive sequences.
Hint:
Using the original recursion and the inductive step, you have
$$\begin{equation}\begin{aligned} b_{n+1} & = 3b_{n} - 1 \\ & = 3\left(\frac{3^n + 1}{2}\right) - 1 \\ & = \left(\frac{3^{n+1} + 3}{2}\right) - \frac{2}{2} \\ & = \frac{3^{n+1} + 1}{2} \end{aligned}\end{equation}\tag{1}\label{eq1A}$$
This is the same was you would get from your proposed formula for $n + 1$.