Cardinality of set of functions Let $\mathbb{N}=\{0,1,2,\ldots\}$ and we consider the following set:
$$\{f:\mathbb{N}\longrightarrow\mathbb{N} \mid\forall n\in\mathbb{N} \ , f(n)=f(n+1)+f(n+2)\}$$
I can tell that this set has at least one element $f:\mathbb{N}\to\mathbb{N}$ such that $f(n)=0$ but can we say more about its cardinal? and what would happen in the case of decreasing functions
 A: Take $a,b\in\Bbb N$. Then consider the function $f\colon\Bbb N\longrightarrow\Bbb N$ such that:

*

*$f(0)=a$;

*$f(1)=b$;

*$f(2)=-f(1)+f(0)=-b+a$;

*$f(3)=-f(2)+f(1)=2b-a$
and so on. So, $f$ belongs to your set and, clearly, every element form your set can be obtained by this process. But then$$n>0\implies f(n)=(-1)^n\left(F_{n-1}a-F_nb\right),$$where $F_n$ is the $n$th Fibonacci number (this can be proved by induction), with $F_0=0$ and $F_1=1$. But then, unless $a=b=0$, you will always have $f(n)<0$ for some $n\in\Bbb N$. So, your set consists only of the null function.
A: Let $f$ be a function in the given set. Then for some fixed $n$:
$$
\begin{aligned}
f(0) &= f(1)+f(2)\ ,\\
f(1) &= f(2)+f(3)\ ,\\
f(2) &= f(3)+f(4)\ ,\\
f(3) &= f(4)+f(5)\ ,\\
f(4) &= f(5)+f(6)\ ,\\
&\qquad\text{ and so on up to}\\
f(n) &= f(n+1)+f(n+2)\ .
\end{aligned}
$$
We add and get:
$$
f(0) = f(2)+f(3)+f(4)+\dots + f(n) + \text{ some more terms}\ .
$$
The value $f(0)$ is finite, on the R.H.S we have integer terms $\ge 0$, so only finitely many are $\ne 0$. So starting with some index, all "terms" are zero. Now we proceed inductively from this index backwards to see that all values of $f$ are zero.
