I've been asked to prove that there exists a $c>1$ such that $f(n)=\Theta(c^n)$ with $f$ mapping to a Fibonacci(-esque, $f(1)$ is 1 and not 0) sequence, so $f(1)=1$, $f(2)=1$ and $f(n)=f(n-1)+f(n-2)$ for any larger $n\in\mathbb{N}$. However, I've been asked to do so without arriving at the closed form formula for the function $f$, so no generating functions, characteristic polynomials, etc. (I'm not allowed to just "guess" the golden ratio, either: I need to "reach it".)
Every method I come up with pushes me in that direction (even before I knew what a characteristic polynomial even was) and I'm pretty stumped. Would appreciate any cool ideas.
We are looking for $A,B,c>0$ such that $Ac^n\le f(n)\le Bc^n$. Let $n\ge2$ and suppose that these inequalities hold for $n$ and $n-1$. Then $$f(n+1)=f(n)+f(n-1)\le Bc^{n-1}(1+c).$$ This upper bound will be at most $Bc^{n+1}$ if $c>0$ is chosen so that $c^{n-1}(1+c)\le c^{n+1}$, i.e., $c^2\ge1+c$.
Similarly, $$f(n+1)\ge Ac^{n-1}(1+c),$$ and this lower bound will be at least $Ac^{n+1}$ if $c^2\le1+c$.
Hence we see that if we take $c>0$ such that $c^2=c+1$, then we can do the induction step. I let you initialize the induction by choosing $A,B>0$ appropriately given the values of $f(1)$ and $f(2)$.