Please help solve this question for me.
(a)Use mathematical induction to show that
S(n) = 3 × 2 n-1 -2
is the solution for the recurrence relation:
T(n) = 2T(n – 1) + 2 for n > 1 and T(1) = 1
(b) If 1 is added to the recurrence relation such that:
T(n) = 2T(n – 1) + 3 for n > 1 and T(1) = 0
What is the new equation for S(n)?
No, that's NOT what you were asked to do. You were asked to show that a certain function, which we cannot read because you are not using parentheses properly, is a solution to that equation. That is NOT the same as "solving the equation".
You are in Discrete Math and you don't know how to do mathematical induction???
You first prove the base case: Here you need to show that just as . So we know that there exists some k such that is the solution for .
Now you have to show that solves . I have set it up for you all you need to do is simplify the equation below.
-Dan
1.) 2 + 2^2 + 2^3 + 2^4 + ... + 2^n = 2^n+1 -2
Let n=1
2^n+1 -2 = 2^1+1 - 2 = 2^2 -2 = 4 - 2 = 2
assume n=k
2 + 2^2 + 2^3 + 2^4 + ... + 2^k = 2^k+1 -2
Let n=k+1
2 + 2^2 + 2^3 + 2^4 + ... + 2^k = 2^k+1 -2
= [2 + 2^2 + 2^3 + 2^4 + ... + 2^k] + 2^k+1
= [2^k+1 -2] + 2^k+1
= 2 x 2^k+1 - 2
= 2^1 x 2^k+1 - 2
= 2^k+1+1 - 2
= 2^(k+1)+1 - 2
Is this correct?
I have come across the exact same question as part of my assignment. For part b:
My solution should be: S(n)=3(2^n-1) - 1(b) If 1 is added to the recurrence relation such that:
T(n) = 2T(n – 1) + 3 for n > 1 and T(1) = 0
What is the new equation for S(n)?
Is this correct? Then I can just prove using the same induction method as above?
You didn't prove anything that has to do with your problem.
Okay. Step by step. First we need to establish a "base case." S is supposed to be a solution to the T equation, so we start there. The problem says that T_1 = 1. So does S_1 = 1?
Now you can assume that the S solution for the T equation is valid for some specific value of k. Thus we know that S_k solves the T_k equation. In particular we suppose that
is the solution of the equation .
Now we need to show that is the solution for
Can you finish from there?
-Dan