How to prove by this type of question by Induction (If $a_1 = 6$ and $a_{m+1} = 2a_m - 3m + 2$ for $m \geq 1$, then $a_n = 2^n + 3n + 1$)

Question

Please do not tell me how to prove this exact question. I would like to know how to go about proving the following type of question by induction:

If $a_1 = 6$ and $a_{m+1} = 2a_m - 3m + 2$ for $m \geq 1$, then $a_n = 2^n + 3n + 1$

Again, please do not prove this for me, but show me how to prove questions of this type, perhaps through the use of another example.

I did look at using multidimensional induction, but I'm not sure if it's appropriate, and to be honest, I do not fully understand it.

I would greatly appreciate any help,

Thanks.

Answer 1

Start by proving the base case: $a_{1} = 6$. Is the closed form solution satisfied?

Now assume true up to $k > 1$. And prove true for $k+1$. You will want to use the inductive hypothesis on $a_{m}$ and then some algebraic simplifications.

Please do not tell me how to prove this exact question

Um, okay? It would probably be better then for you to pick an example you want to see proven so we can help you push through the steps. We really don't want to come up with different examples if you already have one you are interested in. But the procedure I outlined above is what you want to use (and in general, how weak induction works). If your recurrence is not first-order, you would use strong-induction with the multiple base cases.

Perhaps you will find this tutorial on induction helpful: http://www.dreamincode.net/forums/topic/280815-introduction-to-proofs-induction-and-big-o/