Time Complexity recurrence When we have the recurrence $T(N)=T(N-1)+T(N-2)$, one normally uses $x^N$ and solves for $x$ which gives the golden ratio. But why does one use $x^N$ and not something else, like $\log(N)$ or $N$?
 A: We can "factor" a linear equation with constant coefficients, i.e. transform it to a cascade of first order equations.
Consider the second order equation
$$T_n+rT_{n-1}+sT_{n-2}=0$$
which we rewrite as
$$T_n-(a+b)T_{n-1}+abT_{n-2}=0.$$
Then, let us define an intermediate sequence $R$ such that
$$R_n=T_n-aT_{n-1}.$$
From the definition we have
$$R_n-bR_{n-1}=T_n-aT_{n-1}-b(T_{n-1}-aT_{n-2})=T_n-(a+b)T_{n-1}+abT_{n-2}=0.$$
The solution of 
$$\color{green}{R_n-bR_{n-1}=0}$$ is obviously of the form 
$$\color{green}{R_n=bR_{n-1}=b^2R_{n-2}=b^3R_{n-3}=\cdots=b^nR_0=cb^n}.$$ (This is where the powers are coming from.)
Then we solve
$$T_n-aT_{n-1}=cb^n,$$
which will be the sum of the general solution of the homogeneous equation
$$T_n-aT_{n-1}=0$$ i.e. $$T_n=c'a^n,$$ and a particular solution of the non-homogeneous equation which can be 
$$c''b^n.$$
Indeed,
$$T_n-aT_{n-1}=c''b^n-ac''b^{n-1}=c''(1-\frac ab)b^n=cb^n.$$
Hence,
$$T_n=c'a^n+c''b^n.$$
The method extends to equations of any order and one can show that the solution is a linear combination of the $n$-th powers of the roots of the so-called characteristic polynomial (the polynomial obtained by replacing $T_{n+k-d}$ by $x^k$; in the above case, $x^2+rx+s$).
To summarize, the terms $a^n$ come form the solution of some first order homogeneous equation $T_n=aT_{n-1}$.

Note that when the characteristic polynomial has multiple roots, the powers $a^n$ aren't sufficient, and you need to consider terms of the form $n^ma^n$.
You may also find roots which are complex, and you will need terms like $r^n\cos(n\theta)$ and $r^n\sin(n\theta)$.
