Thread: Im having trouble with mathematical induction

1. Im having trouble with mathematical induction

(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)?

2. Re: Im having trouble with mathematical induction

Originally Posted by carlosgalhos
S(n) = 3 × 2 n-1 -2
What is this line? I can't make heads nor tails out of it.

-Dan

Edit: Ah I see now. $\displaystyle S_n = 3 \left ( 2^{n-1} \right ) - 2$. Please use parenthesis.

3. Re: Im having trouble with mathematical induction

Originally Posted by topsquark
What is this line? I can't make heads nor tails out of it.

-Dan
That doesnt matter
I just need to prove that n>1 statement is true

Just need to solve this equation and prove that its true: T(n) = 2T(n – 1) + 2 for n > 1 and T(1) = 1

4. Re: Im having trouble with mathematical induction

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".

5. Re: Im having trouble with mathematical induction

Originally Posted by carlosgalhos

(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
You can easily prove the base case, so I'll skip it.

Assume that we know $\displaystyle S_k = 3 \left ( 2^{k-1} \right ) - 2$ for some k.

We need to show that $\displaystyle S_{k + 1} = 3 \left ( 2^k \right ) - 2$ solves $\displaystyle T_{k + 1} = 2 T_k + 2$

So plugging things in we need to show that
$\displaystyle 3 \left ( 2^k \right ) - 2 = 2 \left [ 3 \left ( 2^{k-1} \right ) - 2 \right ] + 2$

Can you take it from here?

-Dan

6. Re: Im having trouble with mathematical induction

Originally Posted by topsquark
You can easily prove the base case, so I'll skip it.

Assume that we know $\displaystyle S_k = 3 \left ( 2^{k-1} \right ) - 2$ for some k.

We need to show that $\displaystyle S_{k + 1} = 3 \left ( 2^k \right ) - 2$ solves $\displaystyle T_{k + 1} = 2 T_k + 2$

So plugging things in we need to show that
$\displaystyle 3 \left ( 2^k \right ) - 2 = 2 \left [ 3 \left ( 2^{k-1} \right ) - 2 \right ] + 2$

Can you take it from here?

-Dan
Can you finished please as i dont really understand this question at all.

7. Re: Im having trouble with mathematical induction

Originally Posted by carlosgalhos
Can you finished please as i dont really understand this question at all.
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 $\displaystyle S_1 = 1$ just as $\displaystyle T_1 = 1$. So we know that there exists some k such that $\displaystyle S_k$ is the solution for $\displaystyle T_k$.

Now you have to show that $\displaystyle S_{k + 1}$ solves $\displaystyle T_{k + 1}$. I have set it up for you all you need to do is simplify the equation below.

-Dan

8. Re: Im having trouble with mathematical induction

Originally Posted by topsquark
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 $\displaystyle S_1 = 1$ just as $\displaystyle T_1 = 1$. So we know that there exists some k such that $\displaystyle S_k$ is the solution for $\displaystyle T_k$.

Now you have to show that $\displaystyle S_{k + 1}$ solves $\displaystyle T_{k + 1}$. 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?

9. Re: Im having trouble with mathematical induction

I have come across the exact same question as part of my assignment. For part b:
(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)?
My solution should be: S(n)=3(2^n-1) - 1

Is this correct? Then I can just prove using the same induction method as above?

10. Re: Im having trouble with mathematical induction

Originally Posted by carlosgalhos
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?
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
$\displaystyle S_k = 3(2^{k - 1}) - 2$ is the solution of the equation $\displaystyle T_k = 2T_{k - 1} + 2$.

Now we need to show that $\displaystyle S_{k + 1} = 3(2^k) - 2$ is the solution for $\displaystyle T_{k + 1} = 2T_k + 2$

Can you finish from there?

-Dan

11. Re: Im having trouble with mathematical induction

Originally Posted by wilson208
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

Is this correct? Then I can just prove using the same induction method as above?
For this one I think you have to solve the recurrence. There's no method that I know of that will get you the answer based on part a. (But I could be wrong.)

Anyway I got $\displaystyle S_n = 3(2)^{n - 1} - 3$ by solving the recurrence directly.

-Dan