Question

Consider the following recurrence relation.
B(n) = 2 if n = 1
3 · B(n − 1) + 2 if n > 1
Use induction to prove that
B(n) = 3n − 1.
(Induction on n.) Let f(n) = 3n − 1.
Base Case: If n = 1, the recurrence relation says that B(1) = 2, and the formula says that
f(1) = 3 ___-1=___, so they match.
Inductive Hypothesis: Suppose as inductive hypothesis that B(k − 1) = ___ for some
k > 1. Inductive Step: Using the recurrence relation, B(k)=3 · B(k − 1) + 2, by the second part of the recurrence relation:
=3(______)+2, by inductive hypothesis.
= (3^k − 3) +

Answer 1

so, by induction, B(n) = f(n) for all n ≥ 1.

Answer 2

@Loser66 :)

Answer 3

@e.mccormick

Answer 4

What do you think? @e.mccormick

Answer 5

I remember we did this at one point... you found a base case, and that gives you a function with result. then you prove a +1 case. Just don't remember all the steps after that.

Answer 6

oh, I got it, quite unclear with my honey explanation.
ok, rearrange,

Answer 7

\[P_n =3 P_{n-1}+2 \] with \[P_1= 2\]
and you have to construct P_n depends on P_1 only, first. and then prove that P_n

Answer 8

got what I mean? since you have P_n depends on P_n-1 . cannot prove from that, must come up with P_n by P_1

Answer 9

@e.mccormick you know what I mean?

Answer 10

@malia667 how far you go from the class? still apply P_1 , P_2 ,P_3.... P_n or use generating function?

Answer 11

or characteristic equation?

Answer 12

hey hey hey, all friends, reply me please.

Answer 13

On page 5 of this: http://www.math.dartmouth.edu/archive/m19w03/public_html/Section4-2.pdf

There is an inductive proof of a recursion. That should help show the form that Loser66 is talking about.

Answer 14

ok thanks guys.. let me try this..