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}})$