Suppose a function is expressed by: $f(x)=f(x+1) - f(x-1)$ and $f(16)=20 , f(20)=16$ What is $f(20162016)$?

Question

Math quiz bee question

Suppose a function is expressed by:
$$f(x)=f(x+1) + f(x-1)$$ and $$f(16)=20 , f(20)=16.$$ What is $f(20162016)$?

---

Attempt at solution:
$f(17)+f(15)=20$
$f(21)+f(19)=16$
And if I continue it, I can get the values of $f(21)$ and the other integers near it, but how can I get to the value of $f(20162016)$?

This question was from a recent national quiz bee in my place, it is only for $30$ seconds.

The correct answer that they said was $-36$.

Edit 1: As some pointed out, I think I remembered it wrong and the question was: $$f(x)=f(x+1)+f(x-1)$$

Answer 1

If the question is as stated, the answer will have millions of digits because it is a Fibonacci-like series.
If the question is $f(x)=f(x+1)+f(x-1)$, then it repeats every six terms.

Answer 2

For the originally posted question, $f(x)=f(x+1)-f(x-1)$

Rearranging, we have the recurrence relation $f(x+1)=f(x)+f(x-1)$

Looking at its characteristic polynomial, it is of the form $\lambda^2=\lambda+1$

Solving for $\lambda$, we get $\lambda = \frac{1+\sqrt{5}}{2}$ and $\frac{1-\sqrt{5}}{2}$ as the solutions. This implies that $f(x)$ will be of the form:

$$f(x)=\alpha\left(\frac{1+\sqrt{5}}{2}\right)^x + \beta\left(\frac{1-\sqrt{5}}{2}\right)^x$$

for some values of $\alpha$ and $\beta$ to be determined based on our initial conditions.

Using $f(16)=20$ and $f(20)=16$, we can create a system of two equations with two unknowns.

$\begin{cases}20 = \alpha (\frac{1+\sqrt{5}}{2})^{16}+\beta (\frac{1-\sqrt{5}}{2})^{16} = \alpha(\frac{2207+987\sqrt{5}}{2}) + \beta(\frac{2207-987\sqrt{5}}{2})\\ 16 = \alpha(\frac{1+\sqrt{5}}{2})^{20}+\beta(\frac{1-\sqrt{5}}{2})^{20} = \alpha(\frac{15127+6765\sqrt{5}}{2})+\beta(\frac{15127-6765\sqrt{5}}{2})\end{cases}$

Solving is tedious from this point on, but can be done. Once you have calculated $\alpha$ and $\beta$, you can simply plug in whatever value of $x$ you like and finish the messy arithmetic to get a final answer.

Wolfram Alpha tells us that the final form of the equation can be simplified to $f(x)=19918L(x)-44538F(x)$ where $L(x)$ and $F(x)$ represent the $x^{th}$ Lucas and Fibonacci numbers respectively.

---

In the event that the equation was instead intended to be $f(x)=f(x+1)+f(x-1)$, rearranging gives us $f(x+1)=f(x)-f(x-1)$ and characteristic polynomial $\lambda^2=\lambda-1$.

This gives us solutions $\frac{1+\sqrt{-3}}{2}$ and $\frac{1-\sqrt{3}}{2}$, well known numbers as they are the two primitive cube roots of negative one.

We expect our solution to be of the form $f(x)=\alpha\left(\frac{1+\sqrt{-3}}{2}\right)^x + \beta\left(\frac{1-\sqrt{-3}}{2}\right)^x$ for some $\alpha$ and $\beta$ to be determined from our initial conditions.

$\begin{cases}20 = \alpha(\frac{1+\sqrt{-3}}{2})^{16} + \beta(\frac{1-\sqrt{-3}}{2})^{16}=\alpha(\frac{-1-\sqrt{-3}}{2}) + \beta(\frac{-1+\sqrt{-3}}{2})\\ 16 = \alpha(\frac{1+\sqrt{-3}}{2})^{20}+\beta(\frac{1-\sqrt{-3}}{2})^{20} = \alpha(\frac{1-\sqrt{-3}}{2})+\beta(\frac{1+\sqrt{-3}}{2}) \end{cases}$

Solving will give you $\alpha=-2+6i\sqrt{3}$ and $\beta = \frac{4(\sqrt{3}-5i)}{\sqrt{3}+i}$

Plugging back into the equation, and plugging in your desired $x$ value, you can then find the value. In particular $x=20162016$

Answer 3

For $f(x) = f(x+1) + f(x-1)$, one can get (as was shown in the previous answer) the following characteristic equation $\lambda^2-\lambda +1 = 0$, which yields $\lambda_{1,2} = \frac{1\pm i\sqrt{3}}{2} = e^{\pm i \frac{\pi}{3}}$. Then the overall for the function is defined as

$f(x) = \alpha e^{ ix \frac{\pi}{3}} + \beta e^{ -ix \frac{\pi}{3}}$,

and using given conditions ($f(16) = 20$ and $f(20) = 16$) one can find $\alpha,\beta = -18\pm \frac{2i}{\sqrt{3}}$. Finally, plugging $x=20162016$, one will indeed find

$f(20162016) = -36$.

Answer 4

Alternatively, you could make a table using the recurrence you've found with $f(x+1)=f(x)-f(x-1)$, and, after completing for $f(17),f(18),f(19)$, see that a recurrence arises.

\begin{array} {|r|r|} \hline x &16 &17 &18 &19 &20 &21 &22 &23 \\ \hline f(x) &20 &-16 &-36 &-20 &16 &36 &20 &-16 \\ \hline \end{array}