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$?
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}$$
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.
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:
The natural numbers $\mathbb{N}$ form a discretely ordered semiring.
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:
- $f(0) = 0$.
- $f(1) = 1$.
- $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.
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).$$
Proof without induction
First we have : $$F_{n+20}=F_{n+19}+F_{n+18}=2F_{n+18}+F_{n+17}= 3F_{n+17}+2F_{n+16}$$
If you continue reducing this $20$ times you will have: $$F_{n+20} = 10946 F_{n}+ 6765 F_{n-1} \tag {*}$$
and from here you can see that:
$$F_{n+20}\equiv F_n \mod 5 $$
Note The formula $(*)$ could be computed $\mod 5$ which reduces large numbers but it will take some time to finish the calculus, in fact it's the part of a general formula which can be proved by induction : $$F_{p+q}=F_pF_{q+1}+F_{p-1}F_q $$ (take $p=n$ and $q=20$)
Response to comments about induction
If a sequence is defined by induction, then this does not mean that we have to use induction to prove every fact about this sequence. let's take for example the Fibonacci sequence, does one need induction in order to prove that $F_2=1$ or that $F_3 = 2$? of course no . Actually we can formalize the definition in two statements: $$ \begin{align} (1) && F_0=0 , && F_1=1 \\ (2) && \forall n \in \mathbb{N} && F_{n+2}=F_{n+1}+F_n\end{align}$$
so from the first assertion we can prove directly that (without induction) that $F_2=1,F_3=2,F_4=3,\cdots$, and from the second assertion we can prove directly that $\forall n \in \mathbb{N}\ \ \ F_{n+3}=F_{n+1}+2F_{n}$ and $$(3)\ \ \ \ \ \ \forall n\in \mathbb{N}\ \ \ \ F_{n+20}\equiv F_n \mod 20$$
If we want to be more precise, we will say that we can prove without induction that "every sequence $(F_n)_{n\in \mathbb{N}}$ verifying $(2)$ must verify also $(3)$", and more formally: $$\forall (F_n)\in \mathbb{N}^{\mathbb{N}} \ \ \ \ \big(\left(\forall n \in \mathbb{N} F_{n+2}=F_{n+1}+F_n\right)\implies\left(\forall n\in \mathbb{N} F_{n+20}\equiv F_n \mod 20\right)\big) $$
(and here we don't now if $F_n$ is defined uniquely to prove it we must use induction)
"Without using X" questions are always a little dubious - they often boil down to "how well can you hide the X". One obvious approach to this one is to consider the pairs of reminders of successive Fibonacci numbers modulo $5$. The starting point is $(0,1)$, and the successor of $(a,b)$ is $(b,a+b\ mod\ 5)$. This gives the cycle
$(0,1)\to(1,1)\to(1,2)\to(2,3)\to(3,0)\to(0,3)\to(3,3)\to(3,1)\to(1,4)\to(4,0)\to(0,4)\to(4,4)\to(4,3)\to(3,2)\to(2,0)\to(0,2)\to(2,2)\to(2,4)\to(4,1)\to(1,0)\to(0,1)$
of length $20$. But again, this is just a fancy representation of an underlying inductive argument.
$$\begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n - 1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n$$
So
$$\begin{align} \begin{bmatrix} F_{n+21} & F_{n+20} \\ F_{n+20} & F_{n + 19} \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{20 + n} &\pmod 5 \\ % &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{20} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n} &\pmod 5 \\ % &= \begin{bmatrix} 10946 & 6765 \\ 6765 & 4181 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n} &\pmod 5 \\ % &= \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n} &\pmod 5 \\ % &= \begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n - 1} \end{bmatrix} &\pmod 5 \\ \end{align}$$
Other cycles can be found similarly, for example
$$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{24} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \pmod 6$$
Giving a cycle of length $24$ modulo $6$.
While it doesn't show the precise result ($F_n\equiv F_{n+20}$) that's being looked for, here's a proof that $F_n$ must be periodic mod $5$ — or in fact to any base — using an entirely different approach:
The value of $F_{n+1}$ is some polynomial function of the two previous values $F_n$ and $F_{n-1}$, $F_{n+1}=f(F_n, F_{n-1})$ (in this case, $f(a,b)=a+b$, but that's not actually germane here); therefore this also holds true $\bmod 5$. But now there are at most $5\cdot 5=25$ possible values of the pair $\langle F_{n-1}, F_n\rangle$ — so by the pigeonhole principle, within at most 25 iterations we'll hit a pair of arguments to $f()$ that we've seen before. But since the inputs to the function are the same, the output will be the same, and then the function is periodic with this period.
Note that this argument doesn't care what the function is —, or the modulus it holds for any recurrence relation where the value of $R_{n+1}\bmod m$ is dependent on only the values $\mod m$ of the previous two terms $R_n$ and $R_{n-1}$ (or more generally, where it's dependent on the previous $k$ terms, for some constant $k$).
(This is @mathlove 's solution slightly streamlined.)
The sequence $$G_n:=F_{n+5}-3F_n\qquad({\rm mod} \ 5)$$ satisfies the same recursion as the $F_n$. Furthermore one easily checks that $G_0=G_1=0$. This implies $G_n=0$ for all $n$, so that $$F_{n+5}=3F_n \qquad({\rm mod} \ 5)$$ for all $n$. It follows that $$F_{n+20}=3^4 F_n =F_n\qquad({\rm mod} \ 5)$$ for all $n$.
Unlike most of the answers above this ones derives the length of the period instead of just verifying the conjecture. I believe this is the spirit of not using induction, because induction can sometimes be used merely as a verification and not as an "explanation".
Start by noticing that $$\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^n \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} F_n \\ F_{n+1} \end{bmatrix} $$ and let $S = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}$
All numbers are in $\mathbb F_5$. Computing powers of $S$ is easy if you can diagonalize it. So we start by finding the characteristic polynomial which is $\lambda^2 - \lambda - 1 = (\lambda + 2)^2$. This shows that the only eigenvalues are $-2$. If $S$ were diagonalizable then $S$ would be a multiple of the identity matrix, which it isn't. Therefore we use $S$'s Jordan normal form instead, which is $\begin{bmatrix} -2 & 1 \\ 0 & -2\end{bmatrix}$. Now notice that matrices of the form $\begin{bmatrix} a & b \\ 0 & a\end{bmatrix}$ form a ring, and the determinant of such matrices is $a^2$, so the unit group of that ring has order $20$ (the number of $(a,b) \in \mathbb F_5^2$ pairs for which $a^2 \neq 0$). By Lagrange's theorem, $S^{20} = I$.
You could also just list the first twenty or so terms of the sequence by adding consecutive terms and reducing mod $5$:
$$1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1,1,2 \ldots$$
at which point we have $F_{21} = F_1$ and $F_{22} = F_2$ and therefore the sequence begins to repeat.
Since you asked for non-inductional ways, i'll use an expression attributable to François Édouard Lucas: $$ f_n =\frac{\left(\phi \right)^n - \left(1- \phi \right)^{-n}}{\sqrt5} $$ $$ We´re \space looking\space for \space a \space difference(D) \space such\space that \qquad{D \equiv0 \mod 5}\qquad \qquad Note\space that \qquad{ D= f_{n+20}- f_n=\frac{\left(\phi \right)^{n+20} - \left(1- \phi \right)^{-(n+20)}}{\sqrt5}-\frac{\left(\phi \right)^n - \left(1- \phi \right)^{-n}}{\sqrt5}=\left( \frac{\left(\phi \right)^{10} - \left(1- \phi \right)^{-10}}{\sqrt5} \right) \left({\left(\phi \right)^{n+10} - \left(1- \phi \right)^{-(n+10)}}\right)=(f_{10})\left({\left(\phi \right)^{n+10} - \left(1- \phi \right)^{-(n+10)}}\right)} $$ $$ but\qquad 5\mid (f_{10}=55) \Longrightarrow 5\mid D\Longrightarrow{f_n≡f_{n+20}(mod5)} $$
Your approach to prove a theorem usually depends on how you define things. As Elaqqad said, you can't get rid of induction when you define the Fibonacci sequence by Induction. But if you define Fibonacci sequence from the start with no induction, you can prove some of its features without induction.
I usually suggest to be pragmatic, and accept mathematical induction. But, as you wish, I DO prove Fibonacci sequence is periodic mod 5 without using induction.
Let's start from a non-inductive definition of Fibonacci sequence. I use Binet's formula, as a closed-form expression of the Fibonnaci number.
Fibonnaci number is defined as a function of $n$, which outputs an Integer, and defined as*:
$F[n] := \cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1-\sqrt{5}}{2}\right)^n$
We are about to show $$F_{n}\equiv F_{n+20}\pmod 5$$ for all $n \geq 2$
Actually, we also calculate the reminder. We prove that:
$F[n+20]-F[n]=10945.F[n]+6765F[n−1]$
Doing this is really cumbersome. You can't do this by hand, but using a computational software program like Mathematica as a form of Automated theorem proving you can do it easily:
Define the functions as above statement, and do this in Mathematica:
Simplify[f[n + 20] - f[n] - 10945 f[n] - 6765 f[n - 1]]
and you get exact zero:
0
which compeltes the proof.
I'm trying to extract the exact intermediatory simplifying steps from Mathematica. I'll post it as soon as I get it.
* I am not going to prove that F(n) is actually an integer here.
