# 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

• Not a full answer, but note this is equivalent to the condition that $f(n + 2) = f(n) - f(n + 1)$, so the function is recursively defined by its first two values. Thus, your cardinality is at most $|\mathbb{N}^2| = \aleph_0$. – Duncan Ramage Jan 27 at 18:55
• @DuncanRamage using that $f(n+2)=f(n)-f(n+1)\in\mathbb{N}$, we would have 2 cases, correct? 1) $f(n)=f(n+1)$, in this case, $f$ is constant (zero). 2) $f(n)>f(n+1)$ – math_fc Jan 28 at 0:20
• in the second case, would this mean that such functions could not exist? – math_fc Jan 28 at 0:22

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.

• I'm not fully convinced. How do we know that $f(n) - f(n + 1)$ is not negative eventually? That is, how do we know every choice of $a$ and $b$ will actually define a function into the naturals? – Duncan Ramage Jan 27 at 18:56
• @DuncanRamage Yes, I missed that. Sorry about that. I suppose that it is correct now. – José Carlos Santos Jan 27 at 19:16

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.