42
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ @Timbuc, as far as I can see, isn't the OP asking for non-induction techniques to prove this result? @ op You might want to clear up your title and body to say "use non-induction techniques/methods" instead of what you currently have. $\endgroup$ – Zain Patel Jul 12 '15 at 11:23
  • 2
    $\begingroup$ Now I see the non-induction thing, thanks. BTW, I've no idea what other methods can be used to prove such a result, but that's my problem... $\endgroup$ – Timbuc Jul 12 '15 at 11:31
  • 9
    $\begingroup$ Note. to answer the question in the title is easy: there are only finitely many possible pairs mod(5) so as you list the Fibonacci numbers mod (5), at some point a pair has to recur. Of course, this does not tell you what the period is...only that it is periodic. $\endgroup$ – lulu Jul 12 '15 at 12:23
  • 2
    $\begingroup$ @lulu but you can know the max period is 25 because that's how many pairs of numbers there are mod 5. $\endgroup$ – ratchet freak Jul 12 '15 at 12:30
  • 2
    $\begingroup$ I believe everyone is missing the obvious interpretation, "present a proof that can be followed by a student that doesn't know induction". Obviously integers are inductively defined, that doesn't mean that all proofs have to start there. $\endgroup$ – DanielV Jul 13 '15 at 20:49

13 Answers 13

79
$\begingroup$

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}$$

$\endgroup$
  • 5
    $\begingroup$ Also using concealed induction but very nice imo. +1 $\endgroup$ – Timbuc Jul 12 '15 at 11:40
  • 40
    $\begingroup$ @Timbuc I don't see the induction here. This answer directly applies the definition for several values of n. $\endgroup$ – Christian Semrau Jul 12 '15 at 11:54
  • 13
    $\begingroup$ @ChristianSemrau As noted in other comments, the very definition of the Fibonacci sequence is inductive, so you can't avoid that... $\endgroup$ – Timbuc Jul 12 '15 at 12:14
  • 16
    $\begingroup$ @Timbuc, this answer does not contain induction, it's very clear that if a sequence is defined inductively this does not mean that we must use induction to prove it, take for example the statement $F_3=2$ do we need induction in order to prove it. $\endgroup$ – Elaqqad Jul 12 '15 at 15:06
  • 12
    $\begingroup$ @Timbuc even if it contains $n$ it does not mean that it must be proved by induction : for instance $\forall n \ \ \ \ F_{n+3} =2F_n+F_{n+1}$ does not need induction to be proved, of course we have to admit the definition of Fibonacci numbers $\forall n \ \ \ F_{n+2}=F_{n+1}+F_{n}$ using this you can prove without induction a lot of statements involving $n$. $\endgroup$ – Elaqqad Jul 12 '15 at 15:49
42
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Very elegant, lulu! For those unfamiliar with this approach using the characteristic equation, please see the Wikipedia article on recurrence relations, in particular this theorem, which references the definition of the characteristic polynomial given in this section. $\endgroup$ – PM 2Ring Jul 12 '15 at 12:25
  • $\begingroup$ I suppose that someone might argue that there is a buried induction here. My argument produces a sequence which satisfies the desired recursion and has the right initial values, so I then (implicitly) assert that it coincides with the desired sequence. That is an induction. But, after all, even knowing that the $n^{th}$ term exists is an induction! $\endgroup$ – lulu Jul 12 '15 at 12:37
  • 1
    $\begingroup$ You said: "even knowing that the $n^{th}$ term exists is an induction!". Definitely. And as Peano pointed out, we can say the same thing about the $n^{th}$ term of $N$. :) $\endgroup$ – PM 2Ring Jul 12 '15 at 12:47
  • $\begingroup$ Thank you for this nice answer too +1 $\endgroup$ – user225250 Jul 13 '15 at 3:55
  • $\begingroup$ Very impressive answer ! $\endgroup$ – Hexacoordinate-C Jul 14 '15 at 2:02
41
$\begingroup$

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 ordeerd 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.

$\endgroup$
  • 4
    $\begingroup$ I think this is a very nice answer/clearification of all this mess. +1 $\endgroup$ – Timbuc Jul 13 '15 at 7:02
  • 1
    $\begingroup$ You're correct about Klaus's answer. As he intended it, it does require induction because he essentially claims that since it goes back to the starting $(0,1)$ it must hence repeat. The repetition cannot be proven without induction. As for Jack's answer, if he didn't mention roots of the characteristic polynomial but instead used the right-shift operator, his answer would have been induction-free, because he is doing nothing other than proving a specific instance of the formula in the middle of Elaqqad's answer. Once he talks about real roots he has invoked far more than induction! $\endgroup$ – user21820 Jul 13 '15 at 11:15
  • $\begingroup$ Lulu's answer definitely uses induction because she clearly intends to solve a recurrence via the characteristic equation, same as Christian Blatter's answer. Steven's answer also uses induction since he claims periodicity just from repetition. As for what Jack is using, maybe he did not mean real roots? Who knows? Abstract algebraic extensions with explicit representations should work. $\endgroup$ – user21820 Jul 13 '15 at 11:21
  • $\begingroup$ I've said this below but I think that this nitpicking is missing the point. The spirit of not using induction, as far as I understand it and I may be wrong, is explaining where the result comes from instead of merely verifying it. Induction proofs are sometimes little more than mere verifications. $\endgroup$ – man and laptop Jul 15 '15 at 17:17
  • 1
    $\begingroup$ This is the best answer I've read in a while :-) $\endgroup$ – joriki Jul 16 '15 at 10:34
19
$\begingroup$

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).$$

$\endgroup$
17
$\begingroup$

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)

$\endgroup$
  • 2
    $\begingroup$ How do you know that you can do what your two first lines show for all $\;n\in\Bbb N\;$ ? Of course, induction...though, as in many, many other cases, it is slightly concealed. Anyway, nice going. +1 $\endgroup$ – Timbuc Jul 12 '15 at 11:39
  • 2
    $\begingroup$ @Timbuc The reduction of $F_{n+20}$ works without induction because it directly applies the definition, for different values of n, which is stated to be valid for all n. $\endgroup$ – Christian Semrau Jul 12 '15 at 11:50
  • 2
    $\begingroup$ @Timbuc: The Fibonacci sequence is defined inductively. So in the strictest sense it is impossible to prove it without induction, for when one uses the definition then one "commits" induction :). $\endgroup$ – Megadeth Jul 12 '15 at 12:04
  • 9
    $\begingroup$ The Fibonacci sequence itself is defined inductively. But I don't see where you need induction to prove the statement $(\forall n: F_{n+2}=F_{n+1}+F_{n}) \Rightarrow (\forall n: F_{n+20} \equiv F_n\mod 5)$ $\endgroup$ – Christian Semrau Jul 12 '15 at 12:25
  • 2
    $\begingroup$ I don't understand the talk about 'implicit induction'. The proof method asked for should not use an induction hypothesis, and they don't. Any implicit induction is like saying "Gaussian elimination inverts an $n\times n$ matrix" or "$2^n$ is total" are proved implicitly by induction because they involves natural numbers. $\endgroup$ – Mitch Jul 12 '15 at 16:00
15
$\begingroup$

"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.

$\endgroup$
  • $\begingroup$ It is a bit interesting that only 25 such pairs $(a,b)$ exist, and your cycle accounts for the 20 of them. The trivial sequence $(0,0) \to (0,0)$, a cycle of length one (fixpoint), accounts for 1 more. The last 4 pairs are in a cycle $(1,3) \to (3,4) \to (4,2) \to (2,1) \to (1,3)$. $\endgroup$ – Jeppe Stig Nielsen Jul 14 '15 at 21:10
  • $\begingroup$ Yes; the big cycle consists of those pairs for which $a-2b$ is nonzero (and it gets multiplied by $3$ in each step), while it is $0$ both for the fixpoint $(0,0)$ and the members of the slammer cycle. $\endgroup$ – Klaus Draeger Jul 14 '15 at 21:44
13
$\begingroup$

$$\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$.

$\endgroup$
  • $\begingroup$ Nice answer !,,, +1 $\endgroup$ – user225250 Jul 13 '15 at 4:09
  • 1
    $\begingroup$ Exactly the same as Elaqqad's and Jack's answers, just presented using matrices. It can be helpful to get people to appreciate matrices more... $\endgroup$ – user21820 Jul 13 '15 at 11:23
  • $\begingroup$ Note that it is easy to remove reliance on induction from your answer if you just relate $(F_{n-1},F_n,F_{n+1})$ directly with $(F_{n+19},F_{n+20},F_{n+21})$ instead of going through the $n$-th power of the operator. $\endgroup$ – user21820 Jul 13 '15 at 11:26
  • $\begingroup$ For some reason I like this one the best. Something about the representation as matrices makes this really palatable. $\endgroup$ – Paddling Ghost Jul 13 '15 at 18:28
13
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ That's exactly how I was intending to answer (after first reading the title only, not the question and its specification of $F_{n+20}$). But then, I've been fascinated by modular Fibonacci sequences ever since doing "Fibonacci bracelets" (mod 10) as an "extension" activity at school, twenty-odd years ago. $\endgroup$ – Tim Pederick Jul 14 '15 at 17:25
12
$\begingroup$

(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$.

$\endgroup$
  • 3
    $\begingroup$ Yes this is a good idea, but it uses induction, when you say $G_0=G_1=0$ then $G_n=0$ this can not be proved without induction $\endgroup$ – Elaqqad Jul 12 '15 at 14:55
  • 1
    $\begingroup$ @Elaqqad: It follows from the uniqueness theorem for linear second order recursions. $\endgroup$ – Christian Blatter Jul 12 '15 at 14:58
  • 1
    $\begingroup$ Yes that's true, and hence we used a theorem which is proved by induction. It's true that it's not really very precise what it means not to use induction , I personally don't like questions like : "prove without induction" , it's always better to find the most elegant method without any restriction. $\endgroup$ – Elaqqad Jul 12 '15 at 15:04
  • 4
    $\begingroup$ @Elaqqad: While this answer does require at least one application of an equivalent of the induction axiom, mathlove's answer does not, because once the natural numbers and the fibonacci sequence are given, his answer proves the desired statement directly. But this answer does not as it constructs a new sequence $G$ inductively. $\endgroup$ – user21820 Jul 12 '15 at 17:45
  • 2
    $\begingroup$ @user21820 I agree with that and that's what I'm talking about $\endgroup$ – Elaqqad Jul 12 '15 at 17:56
7
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I'm not up to snuff on my algebra: where did 20 come from? I'm assuming it's because $20=4\cdot 5$, but: "Because the determinant is 4 [what result are you appealing to to conclude?] the unit group of that ring has order 20" $\endgroup$ – Eric Stucky Jul 19 '15 at 0:16
  • 1
    $\begingroup$ @EricStucky The ring of matrices in the form $\begin{bmatrix} a & b \\ 0 & a\end{bmatrix}$ has $25$ elements. The ring is closed under inverses. The invertible elements are precisely those for which $a \neq 0$ because then $\det \neq 0$. Since there are $5$ singular elements (those for which $a = 0$), $20$ are invertible. Then by Lagrange's theorem, $S^{20} = I$ because the Jordan normal form of $S$ is in the unit group of that ring (please say if you want me to explain this). If you want to understand the ring better look at the dual numbers. $\endgroup$ – man and laptop Jul 19 '15 at 8:03
  • $\begingroup$ Okay, so $20=5^2-5$, I see. $\endgroup$ – Eric Stucky Jul 19 '15 at 8:55
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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)} $$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Where is the problem in your question ? have you any specification ? $\endgroup$ – zeraoulia rafik Jul 13 '15 at 15:30
  • $\begingroup$ @zeraouliarafik I have edited my answer substantially to make it more clear. $\endgroup$ – Ho1 Jul 13 '15 at 16:14

protected by Zev Chonoles Jul 13 '15 at 15:31

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?