This is a recursive function: $$f(0) = 0$$ $$f(1) = 1$$ $$f(n) = \frac{f(n - 1) + f(n - 2)}{2}$$ ($n$ is a nonnegative integer.)
I would like to know how I can find: $$\lim_{x \to \infty} f(x)$$
That is the question, below is what I have tried.
I found the answer to be $\frac{2}{3}$ using a small Python program, but I feel like there has to be a better way to do so.
I tried writing out a few terms of the function: $$f(2) = \frac{1}{2}\left( f(1) + f(0) \right)$$ $$f(3) = \frac{1}{4}\left(3f(1) + f(0) \right)$$ $$f(4) = \frac{1}{8}\left(5f(1) + 2f(0) \right)$$
I eventually settled on a function for the numerator $f_n(x)$ and the denominator $f_d(x)$: $$f_n(0) = 0$$ $$f_n(1) = 1$$ $$f_n(n) = f_n(n - 1) + 2f_n(n - 2)$$ $$f_d(n) = 2^{n - 1}$$
Now: $$\lim_{x \to \infty} f(x) = \lim_{x \to \infty} \frac{f_n(x)}{f_d(x)} = \frac{\infty}{\infty}$$ I feel like I have made progress here as I can now use l'Hopital's rule until I get the answer, but for that I need to find the non-recursive definition of $f_n(x)$.
I could also be going down the wrong path here. Wikipedia traversal led me to Limit of a sequence, and Google traversal led me to a page of sequence limit theorems, but I'm not sure what in this information I found is applicable to me.
There are techniques to solve this kind of linear recursive equations similar to linear ODEs with constant coefficients. You can find a solution as a geometric progression $$ f(n)=q^n $$ By plugging into the recursive relation, you get an equation for $q$, $$ 2q^2-q-1=0 $$ which solving gives $q=(1\pm 3)/4=1,-1/2$. The general solution of your second order relation is $$ f(n)=C_1\cdot 1^n+C_2(-1/2)^n=C_1+(-1)^nC_2/2^n $$ Using the initial conditions you get: $0=C_1+C_2$ and $1=C_1-C_2/2$, that is $C_2=-2/3$ and $C_1=2/3$. The final formula is $$ f(n)=\frac 2{3}+\frac{1}{3}\left(-\frac{1}{2}\right)^{n-1} $$ which clearly gives $\lim f(n)=2/3$.