recategorized by
469 views
3 votes
3 votes
how to solve this  T(n)=T(n−1)+T(n−2) if T(0)=T(1)=1
recategorized by

1 Answer

Best answer
2 votes
2 votes

 T(n)=T(n−1)+T(n−2)  //

this reccurreence equation is of form  $a_{n} = a_{n-1} + a_{n-2}$

its homogeneous reccurrence relation

let put , $a_{n} = \alpha ^{r}$

$\alpha ^{r} = \alpha ^{r-1} + \alpha ^{r-2}$

now divide by $\alpha ^{r-2}$   

since r-2 is smallest  degree among r ,r -1 , r-2 so dividing by r-2 

$\alpha ^{2} = \alpha ^{1} +1$

now solve this quadratic 

$\alpha = \frac{1+\sqrt{5}}{2 } , \frac{1-\sqrt{5}}{2 }$

here roots are real and distinct  

general solution $a _{n} = A_{1} \alpha _{1}^{n} + A_{2} \alpha _{2}^{n} + ---$  

$\frac{1+\sqrt{5}}{2 } = \alpha _{1}$

$\frac{1-\sqrt{5}}{2 } = \alpha _{2}$

just put values in general equation we  get  

$a_{n} = ($A_{1}$)  (\frac{1+\sqrt{5}}{2})^{n} + ($A_{2}$)(\frac{1- \sqrt{5}}{2})^{n}$,

now see  image 

A1 ki jaga theta islie because  when we neglect A2 term the whole equation 1 become    =  A1($(\frac{1+\sqrt{5}}{2})^{n}$

A1 is going to be any constant and whhenever two functions differ by constant we say they are theta of each other 

Now  $(\frac{1+\sqrt{5}}{2})$ >$\sqrt{2}$

ab ye sai hai toh  $T(n) = a_{n}= (\frac{1+\sqrt{5}}{2})^n >(\sqrt{2})^n$ (ye bhi sai hai)

finally i can write $(\frac{1+\sqrt{5}}{2})^n = \Omega (\sqrt{2})^n$

or T(n) = $\Omega (\sqrt{2})^n$ = $\Omega (2^{\frac{n}{2}})$

selected by

Related questions

5 votes
5 votes
3 answers
1
sushmita asked Oct 4, 2018
2,119 views
$T(n)=\sqrt{n} T(\sqrt{n})+100n$Please solve this.
0 votes
0 votes
1 answer
2
iarnav asked Jan 11, 2018
405 views
what is the recurrence relation for binary search and linear search?please explain how to derive them.
1 votes
1 votes
0 answers
3
srestha asked May 19, 2019
596 views
Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Co...
1 votes
1 votes
2 answers
4
srestha asked May 10, 2019
846 views
What is the solution of recurrence relation$T\left ( n \right )=T\left ( n-1 \right )+n$