Let $F$ be a function having the property that $F(x+1) = F(x) +F(x-1)$ for every integer $x$. If $F(1)=F(4)=1$, compute $F(10)$.

Question

Let $F$ be a function having the property that $F(x+1) = F(x) +F(x-1)$ for every integer $x$. If $F(1)=F(4)=1$, compute $F(10)$.

I tried to choose values of $x$ that let me use the facts about $F(1)$ and $F(4)$ but I'm still very lost.

Answer 1

We can solve by working our way up to $F(10)$. Starting with $F(3)$, we know that $$ \tag{1} F(3)=F(2)+F(1) $$ and that $$ \tag{2} F(4)=F(3)+F(2) $$ Substituting (1) into (2) we get $$ F(4)=2F(2)+F(1) $$ We know that $F(1)=F(4)$, therefore we know that $F(2)=0$ and thus $F(3)=F(1)=1$. we now know $F(x)\forall x\in\{1,2,3,4\}$, and so you can calculate $F(5)$, then $F(6)$, and so on up until $F(10)$

You should find that $F(3+n)=c_n$ where $c_n$ is the $n$^th Fibonacci number with $c_0=1$, $c_1=1$, $c_2=2$ etc. giving $F(10)=21$

Answer 2

This is a function defined similarly to the Fibonacci sequence (where $F_n=F_{n-1}+F_{n-2}$. Note that: $1=F(4)=F(3)+F(2)=2F(2)+F(1)=2F(2)+1$. Therefore $F(2)=0$. Notice also that $F(5)=2$.

Now we want to compute $F(n)$ with $n\in\mathbb{N}$. One can do so by solving for $F(2)$ and then manually finding $F(10)$. I would like to suggest another solution.

Notice that: $\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}$$\begin{bmatrix} F(4) \\ F(5) \end{bmatrix}=\begin{bmatrix} F(5) \\ F(6) \end{bmatrix}$ and one can prove by induction that $\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^n\begin{bmatrix} F(4) \\ F(5) \end{bmatrix}=\begin{bmatrix} F(4+n) \\ F(5+n) \end{bmatrix}$

So one only needs to calculate, in this case, the $6th$ power of $\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}$. If you're familiar with diagnolization, $A=\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}$ is diagonalizable and therefore its $nth$ power is easily calculated with: $A^n=PD^nP$ where $P$ is the diagonalizing matrix and $D$ is diagonal matrix.

So, calculating gives us: $\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^6\begin{bmatrix} F(4) \\ F(5) \end{bmatrix}=\begin{bmatrix} 21 \\ 34 \end{bmatrix}$, giving us $F(10)=21$.

---

It may be that in this case this solution is an overkill for something that can be computed straight-forward, but this is a general idea that can be helpful.

Answer 3

A more general way to solve this problem:

The set of sequences satisfying $A_{n+2}=A_{n+1}+A_{n}$ is a vector space of dimension 2 under the term by term operations. A nice base is $\{(F_n),(F_{n-1})\}$ where $F_n$ is the Fibonacci sequence. Then every sequence with that recurrence relation can be written as $A_n = x F_n + y F_{n-1}$ for some $x,y$.

In this particular case, we have $A_1=1$ and $A_4 = 1$, which gives the equations we need to calculate $x$ and $y$:

• $1 = A_1 = x F_1+y F_0 = x$
• $1 = A_4 = x F_4+y F_3 = 3x+2y$

This leads to $x=1, y=-1$, so $A_n = xF_n+yF_{n-1} =F_n-F_{n-1}= F_{n-2}$

Answer 4

A more elementary/intuitionistic solution than the others (which use recursion and matrices). My aim is to rewrite the problem in language that a talented 11-year-old could solve.

Once we recognise that the sequence $F(1),F(2),F(3),F(4),\dots$ is a Fibonacci sequence (not necessarily starting at $1,1$), let's just look at the gaps we're trying to find and see what jumps out: $$1,\ \_\_,\ \_\_,\ 1,\ \_\_, \ \dots$$

My problem is now:

1. Find the missing numbers in the first two gaps.
2. Continue the sequence (until we have found $10$ terms).

You can solve this problem by trial and error, but with a tiny bit of algebra we can prove uniqueness of the solution.

If I call my first two gaps $x$ and $y$, then we know that $1+x=y$ and $x+y=1$ (because the term-to-term rule is that each term is the sum of the two previous terms).

Because $y$ is $1$ more than $x$, I can rewrite the second equation as $x+(x+1)=1$. That is, $2x=0$ and $x=0$. So $y=1$.

So the sequence is $$1,\ 0,\ 1,\ 1,\ \_\_, \ \dots$$

Now we can even notice that this is the canonical Fibonacci sequence exactly, but with two extra terms ($1,0$) at the beginning (or maybe $3$ more, depending on your definition).

Either way, carrying on the sequence is no problem.

Answer 5

As I have shown previously here, the general solution to the sequence $f_n=af_{n-1}+bf_{n-2}$ can be expressed as

$$ f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{f_0}{2} (\alpha^n+\beta^n) $$

where $\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$.

Since this is Fibonacci sequence, $\alpha,\beta=\varphi,-1/\varphi$ and you can get your solution directly for any initial conditions.