$Proof by induction the following recursive equation$

Question

$Proof by induction the following recursive equation$

Master-theorem is not allowed, I need it showed by induction weather one of the 1,2,3 is right. Pls step by step.

Discrete Mathematics

Tn2910

15

Report

Tn2910

+1

nobody? more bounty or what? cant be that hard for specialists
- Mathe
  
  0
  
  Are you sure those are the right possible answers? Because it looks to me the problem is O(log n)
Savionf

0

This is a very time consuming problem. Can you increase the bounty to $20?
- Tn2910
  
  0
  
  yes i can, but the website doesnt allow me too, i will open a new one.
- Savionf
  
  0
  
  Are you sure, you should be able to increase the bounty from the side box.
Savionf

0

I meant are you sure?
- Savionf
  
  0
  
  Or I can answer this one and you can leave a tip after.
- Tn2910
  
  0
  
  i increased the bounty but please solve it with induction, maste theorem is not allowed for me and pls step by step, so i can also understand it

Answer

The answer is accepted.

Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.

Tn2910

+1

nobody? more bounty or what? cant be that hard for specialists

Mathe

0

Are you sure those are the right possible answers? Because it looks to me the problem is O(log n)
Mathe

0

Are you sure those are the right possible answers? Because it looks to me the problem is O(log n)
Savionf

0

This is a very time consuming problem. Can you increase the bounty to $20?

Tn2910

0

yes i can, but the website doesnt allow me too, i will open a new one.

Savionf

0

Are you sure, you should be able to increase the bounty from the side box.
Tn2910

0

yes i can, but the website doesnt allow me too, i will open a new one.
Savionf

0

Are you sure, you should be able to increase the bounty from the side box.
Savionf

0

I meant are you sure?

Savionf

0

Or I can answer this one and you can leave a tip after.

Tn2910

0

i increased the bounty but please solve it with induction, maste theorem is not allowed for me and pls step by step, so i can also understand it
Savionf

0

Or I can answer this one and you can leave a tip after.
Tn2910

0

i increased the bounty but please solve it with induction, maste theorem is not allowed for me and pls step by step, so i can also understand it

Answer 1

Answers can only be viewed under the following conditions:

The questioner was satisfied with and accepted the answer, or
The answer was evaluated as being 100% correct by the judge.

View the answer

We prove by induction that

$$(1) T_2(2^m)=3 (2^m)^2-2^m.$$

For $m=0$ we have
\[2=T_2(2^0)=3(2^0)^2-2^0=3-1 \Rightarrow 2=2.\]
Hence (1)holds for $m=0$. Suppose (1) holds for $m$. Then

\[T_2(2^{m+1})=4T(2^m)+2^{m+1}=4[3 (2^m)^2-2^m]+2^{m+1}\]
\[=3(2^{m+1})^2-4 \times 2^{m}+2^{m+1}=3(2^{m+1})^2 -2\cdot2^{m+1}+2^{m+1}\]
\[=3(2^{m+1})^2 -2^{m+1}.\]
Thus (1) holds for $m+1$, and by induction it holds for all $m$.

Let $n=2^m$ in (1) to get
\[T_2(n)=3n^2-n.\]
This means that $T_2(n)=\Theta (n^2)$.

***
Here I explain how I got (1)
\[T_2(2^m)=4T_2(2^{m-1})+2^m=4(4T_2(2^{m-2})+2^{m-1})+2^m=4^2T_2(2^{m-2})+4\cdot2^{m-1}+2^{m}\]
\[=4^2[4 T_2(2^{m-3}) +2^{m-2}]+4\cdot2^{m-1}+2^{m}\]
\[=4^3 T_2(2^{m-3})+4^2 \cdot 2^{m-2}+4\cdot 2^{m-1}+2^m.\]

Looking at the above, we can guess the pattern:

\[T_2(2^m)=4^kT_2(2^{m-k})+\sum_{i=0}^{k-1}4^{k}2^{m-k}.\]
Letting $k=m$ we get

\[T_2(2^m)=4^mT_2(2^{0})+\sum_{i=0}^{m-1}4^{k}2^{m-m}\]
\[=4^mT_2(1)+\sum_{i=0}^{m-1}4^{k}2^{m-k}\]
\[=4^mT_2(1)+\sum_{i=0}^{m-1}2^{2k}2^{m-k}\]
\[=4^mT_2(1)+\sum_{i=0}^{m-1}2^{m+k}\]
\[=4^mT_2(1)+2^m\sum_{i=0}^{m-1}2^{k}\]
\[=4^m \cdot 2+2^m\sum_{i=0}^{m-1}2^{k}=4^m \cdot 2+2^m(2^m-1)\]
\[2\cdot 4^{m}+(2^m)^2-2^m=2\cdot (2^{m})^2+(2^m)^2-2^m\]
\[=3\cdot (2^{m})^2-2^m.\]
Hence
\[T_2(2^m)=3\cdot (2^{m})^2-2^m.\]

Savionf

574

Tn2910

0

How do you get this: 3(2^m)^2−2^m in the first equation?
- Savionf
  
  0
  
  I added a proof. This was indeed two questions, and it took me over 1 hour to answer. I would appreciate a good tip.

$Proof by induction the following recursive equation$

Answer

Related Questions

Search