4
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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$. $\endgroup$ – Duncan Ramage Jan 27 at 18:55
  • $\begingroup$ @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)$ $\endgroup$ – math_fc Jan 28 at 0:20
  • $\begingroup$ in the second case, would this mean that such functions could not exist? $\endgroup$ – math_fc Jan 28 at 0:22
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – Duncan Ramage Jan 27 at 18:56
  • $\begingroup$ @DuncanRamage Yes, I missed that. Sorry about that. I suppose that it is correct now. $\endgroup$ – José Carlos Santos Jan 27 at 19:16
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.