Are there infinitely many numbers such that $ \phi(n)=\phi(n-1)+\phi(n-2)$? Euler $\phi(x)$ function. Are there infinitely many solutions $n$ to this equation:
$$ \phi(n)=\phi(n-1)+\phi(n-2)?$$
Here the vector of prime $n$ which satisfy this relation (source OEIS A266164):
[3, 5, 7, 11, 17, 23, 37, 41, 47, 101, 137, 233, 257, 857, 1297, 1601, 2017, 4337, 14401, 16097, 30497, 62801, 65537, 77617, 686737, 18800897, 255080417, 12885295097, 12918324737, 96052225601, 516392008697, 7026644072737] 
 A: I've seen these called Phibonacci numbers. This paper talks about bounding their asymptotic density so presumably there are infinitely many, but I am not familiar with a proof.
They are A065557.
A: I suggest to start with $n=3$ because the definition of $\phi(0)$ might be problematic. If we assume $\phi(0)=0$ however, $n=2$ is a solution as well. Starting with $n=3$, the number of solutions below $10^k$ is :
? for(k=1,7,print(k,"   ",length(select(m->eulerphi(m)==eulerphi(m-1)+eulerphi(m
-2),[2..10^k]))))
1   3
2   9
3   14
4   22
5   31
6   39
7   47
?

With the additional condition that $n$ is composite, the count is as follows :
? for(k=1,7,print(k,"   ",length(select(m->(eulerphi(m)==eulerphi(m-1)+eulerphi(
m-2))*(ispseudoprime(m)==0),[2..10^k]))))
1   0
2   0
3   0
4   4
5   7
6   14
7   22
?

The smallest solution exceeding $10^k$ is :
? for(k=1,7,n=10^k;while(eulerphi(n)<>eulerphi(n-1)+eulerphi(n-2),n=n+1);print(k
,"   ",n))
1   11
2   101
3   1037
4   14401
5   110177
6   1876727
7   10076627
?

Apparently all solutions (besides $n=2$) are odd. Maybe this can be proven.
