MHB Proof by Induction Help: Solving Recursive & Closed Formulas

[Cribs1420]

I am having a heck of a time with this proof. I am given both the recursive and closed formula and am supposed to prove that they are equivalent using induction.

This is what I am given:
b_k = 3b_k-1+2 for k <2 and b₁=2

the closed formula is b_n= 3ⁿ-1Trying to solve it this is as far as I have gotten...

3^m-1 = 3(3^(m-1)-1)) +2

I am not sure if this is the correct approach because I am unable to solve it out. Any suggestions on what I should be doing? Thanks a bunch!

 

[Ackbach]

Are you sure $k \le 2?$ The recurrence relation is solved for the higher term, but if $k \le 2,$ then you'd have to go backwards - quite unusual in recurrence relations.

 

[Evgeny.Makarov]

Assuming it's $k\ge 2$, let's go through the whole procedure for proofs by induction.

First, identify a property $P(n)$ concerning which you need to prove "$P(n)$ for all $n\ge1$". Second, write the base case $P(1)$ explicitly (i.e., without using the symbol $P$) and prove it. Third, in the induction step you need to prove that $P(k)$ implies $P(k+1)$ for all $k\ge1$. Towards this proof, you fix an arbitrary $k\ge1$ and assume $P(k)$: this is the induction hypothesis (IH). Write $P(k)$ explicitly and label it as IH. From this hypothesis, you need to prove $P(k+1)$. Write $P(k+1)$ explicitly and indicate that it is what you need to prove (as opposed to the IH, which is assumed). Finally, try deriving the explicit form of $P(k+1)$ from the explicit form of $P(k)$.

If after doing this you have questions, then post the intermediate results of your work.