How to prove that the Fibonacci sequence is periodic mod 5 without using induction?

The sequence $(F_{n})$ of Fibonacci numbers is defined by the recurrence relation

$$F_{n}=F_{n-1}+F_{n-2}$$ for all $n \geq 2$ with $F_{0} := 0$ and $F_{1} :=1$.

Without mathematical induction, how can I show that $$F_{n}\equiv F_{n+20}\pmod 5$$ for all $n \geq 2$?

Solution 1:

In mod $5$,
$$\begin{align}F_N&\equiv F_{N-1}+F_{N-2}\\&\equiv F_{N-2}+F_{N-3}+F_{N-3}+F_{N-4}\\&\equiv F_{N-3}+F_{N-4}+2(F_{N-4}+F_{N-5})+F_{N-4}\\&\equiv F_{N-4}+F_{N-5}+F_{N-4}+2(F_{N-4}+F_{N-5})+F_{N-4}\\&\equiv 3F_{N-5}\end{align}$$ So, we have

$$\begin{align}F_{n+20}&\equiv3F_{n+15}\\&\equiv 3\cdot 3F_{n+10}\\&\equiv 3\cdot 3\cdot 3F_{n+5}\\&\equiv 3\cdot 3\cdot 3\cdot 3F_{n}\\&\equiv F_n\end{align}$$

Solution 2:

As a different approach, you can just solve the recursion mod(5) exactly. There's a small problem in that the characteristic equation $$\lambda^2=\lambda +1$$ has a double root, 3, mod 5. But the standard device, using $n\lambda^n$ works and we see that the general term, mod (5), is $$F_n=(1+n)3^n$$ You are then asking that $(1+n)3^n = (1 + n + 20)3^{n+20}$ mod (5). But 21 + n = 1+ n and 3 has order 4 so we are done.

Solution 3:

There's been a lot of discussion in this question about whether certain proofs contain a hidden induction, so this answer formalizes what it means for a proof to use induction, and discusses which of the given answers use induction with respect to this formalization.

The natural numbers are defined by the Peano axioms, which can be stated succinctly as follows:

1. The natural numbers $\mathbb{N}$ form a discretely ordered semiring.

2. If $S\subset \mathbb{N}$ has the properties that (i) $0\in S$ and (ii) $(\forall n)(n\in S \Rightarrow n+1\in S)$, then $S=\mathbb{N}$.

In axiom 1, a semiring is similar to a ring, except that elements need not have additive inverses, and saying it's "discretely ordered" means that there's a linear order on $\mathbb{N}$ that satisfies certain axioms. See here for a complete list of axioms contained in axiom 1.

Axiom 2 is the axiom of induction. Axioms 1 and 2 together define Peano Arithmetic (PA), while axiom 1 alone defines a theory similar to the natural numbers in which induction does not necessarily hold. This theory is often denoted $\mathrm{PA}^-$.

So asking whether something can be proven "without induction" is essentially asking whether we can prove the statement in a model for $\mathrm{PA}^-$, i.e. asking whether we can prove the statement for any discretely ordered semiring.

This presents a problem, because it's not clear exactly what the "Fibonacci numbers" refer to in an arbitrary discretely ordered semiring. Here's one possible definition:

Definition. Let $N$ be a discretely ordered semiring. A Fibonacci function on $N$ is a function $f\colon N\to N$ satisfying the following conditions:

1. $f(0) = 0$.
2. $f(1) = 1$.
3. $f(n+2) = f(n+1) + f(n)$ for all $n\in N$.

Here $0$ denotes the additive identity of $N$, and $1$ denotes the multiplicative identity.

Now, it's possible to prove using induction that there exists a unique Fibonacci function on $\mathbb{N}$ (namely the usual Fibonacci sequence), but this isn't possible to prove in an arbitrary discretely ordered semiring $N$. In fact it's possible to prove (in ZFC) that a Fibonacci function always exists, but it won't be unique unless $N$ is isomorphic to $\mathbb{N}$.

However, this doesn't prevent us from proving things about arbitrary Fibonacci functions. Here's a statement and proof of the OP's claim without any induction:

Theorem. Let $N$ be a discretely ordered semiring, and let $f\colon N \to N$ be a Fibonacci function. Then for all $n\in N$, there exists a $k\in N$ so that $$ f(n+20) = f(n) + 5k, $$ where $5$ denotes $1+1+1+1+1$ and $20$ denotes $5+5+5+5$.

Proof: We will follow mathlove's beautiful answer. Before the proof begins, note that $N$ must contain a canonical copy of $\mathbb{N}$, namely the subsemiring generated by $1$. For convenience, we will assume that $\mathbb{N}\subset N$, which lets us use constants like $5$ without explaining that $5$ means $1+1+1+1+1$.

Observe first that $$\begin{align}f(n+5) &= f(n+4)+f(n+3)\\&= f(n+3)+f(n+2)+f(n+2)+f(n+1)\\&= f(n+2)+f(n+1)+2(f(n+1)+f(n))+f(n+1)\\&= f(n+1)+f(n)+f(n+1)+2(f(n+1)+f(n))+f(n+1)\\&= 3f(n) + 5f(n+1)\end{align}$$ for all $n\in N$. Then $$\begin{align}f(n+20)&= 3f(n+15) + 5f(n+16)\\&= 3^2f(n+10) + 5\bigl(3f(n+11)+f(n+16)\bigr)\\&= 3^3 f(n+5) + 5\bigl(3^2 f(n+6)+3 f(n+11) + f(n+16)\bigr)f\\&= 3^4 f(n) + 5\bigl(3^3 f(n+1) + 3^2 f(n+6) + 3f(n+11) + f(n+16)\bigr),\end{align}$$ But $3^4 = 81 = 5(16) + 1$, and hence $$ f(n+20) = f(n) + 5\bigl(16f(n) + 3^3 f(n+1) + 3^2 f(n+6) + 3f(n+11) + f(n+16)\bigr). $$ This proves the given theorem in an arbitrary discretely ordered semiring, with no use of induction.

So mathlove's answer is correct, in the sense that the argument legitimately doesn't use induction.

I suspect that lulu's answer does use induction, although it's hard to tell, because it's harder to see how it can be translated to the context of arbitrary discretely ordered semirings. There's also the problem that exponentiation can't be defined uniquely in an arbitrary ordered semiring. Perhaps what lulu has shown is that there exists a Fibonacci function with the desired property.

Like mathlove's answer, Elaqqad's answer works just fine in an arbitrary discretely ordered semiring, which means that it legitimately doesn't use induction.

Jack D'Aurizio's answer uses Binet's formula, which presumably can't be made to work in an arbitrary discretely ordered semiring, though I suppose it might be possible to recover some version of it. We would have to start by discussing whether an arbitrary discretely ordered semiring can be embedded in some sort of field that contains a square root of five, and in what sense it might be possible to define exponentiation on that field with the exponent being an element of the semiring.

Klaus Draeger's answer of course requires induction, but I suspect that a similar argument could be made to work in general, simply by replacing the initial $(1,0)$ by an arbitrary pair $(a,b)$ and reducing modulo $5N$. (As far as I can tell, we have no idea how large $N/5N$ is in general, but that doesn't mean we can't do calculations in the quotient. Note that using $N/5N$ would have simplified the proof above as well, though it would have increased the conceptual difficulty.)

Christian Blatter's answer uses induction to prove that $G_n=0$ for all $n$. I don't see a way around this.

Solution 4:

Another possible approach. Let $\sigma$ a root of the characteristic polynomial $x^2-x-1$. We have:

$$ \sigma^2 = \sigma+1,\qquad \sigma^4 = \sigma^2+2\sigma+1 = 3\sigma+2, $$ $$ \sigma^8 = 9\sigma^2 + 12\sigma +4 = 21\sigma + 13,\qquad \sigma^{16} = 441\sigma^2 + 546\sigma + 169 = 987\sigma + 610,$$ hence: $$ \sigma^{20} = (3\sigma + 2)(987\sigma + 610) = 6765\sigma + 4181 = \sigma^0 + 55(123\sigma+76).$$ If now we multiply both sides by $\sigma^n$ and use the Binet's formula, we prove the stronger claim:

$$ \forall n\geq 0,\qquad \color{red}{55} \mid (F_{n+20}-F_n).$$