This is the problem that my professor did. For the recursive sequence given belo

Question

This is the problem that my professor did. For the recursive sequence given below, find the explicit formula and prove it using induction: h_k=h_(k-1)+2^k, for all integers k>1, h_1=1

h_k=h_(k-1)+2^k for all integers, k>1. h_1=1 proof by induction:

base step: k=1-> 2^(1+1)-3=1=h_z

inductive step: assume true for k, h_k=2^(k+1)-3 show for k+1 h_(k+1)=h_k+2^(k+1)=2^(2k+1)-3+2^(2k+1) =2^(2k+1)+2^(k+1)-3 =2*2^(k+1)-3 =2^(k+2)-3

This is the new problem that he gave us and hope that you can me with. For the recursive sequence given below, find the explicit formula and prove it using induction: h_k = 2^k - h_(k-1) for all integers k > 0, h_0 = 1

Explanation / Answer

h(k) = 2^(k+1)/3 + ((-1)^k )/3

Base step

h(0) = 2^(0+1)/3 + ((-1)^0)/3 = 2/3 +1/3 = 3/3 = 1

inductive step: assume true for k, h_k=(2^(k+1) )/3+((-1)^k )/3

show for k+1

h_(k+1)= (2^(k+2)) /3 + ((-1)^(k+1))/3

h(k+1) = 2^(k+1) - h(k)

= 2^(k+1) -   ((2^(k+1))/3 + ((-1)^k )/3)

= 1/3* ( 3*2^(k+1) - (2^(k+1)) + ((-1)^k)

=1/3* (2*2^(k+1) - (-1)^k)

=1/3*( 2^(k+2) +(-1)^(k+1))

hence proved

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.