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)$. 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.
 A: 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$
A: 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.
A: 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:

*

*Find the missing numbers in the first two gaps.

*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.
A: 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}$
A: 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.
