0
$\begingroup$

Assume that the sequence of Fibonacci numbers begins with 2 instead of 1,i.e., $$F_1=2,F_2=3,F_3=5,...$$

Let $F_n$ denote the $n^{th}$ Fibonacci number.

Claim 1: $F^2_{n+1} = -1 \mod F_n$.

Claim 2: $F^2_{n} = 1 \mod F_{n+1}$.

I have probably missed something that obvious in the induction step of proof. But I cannot realize it.

Any help or suggestion?

$\endgroup$
  • $\begingroup$ Is above improvement sufficient to clarify question? $\endgroup$ – user530422 Apr 10 '18 at 16:52
  • $\begingroup$ That's fine, I deleted my comment. $\endgroup$ – Mark Bennet Apr 10 '18 at 16:52
1
$\begingroup$

You have $F_n^2-F_{n+1}F_{n-1}=(-1)^{n+1}$ which you should be able to prove, and then use.

With these kind of things it is sometimes worth looking for a stronger statement which is more amenable to the induction you are trying to use.

$\endgroup$
  • $\begingroup$ By taking $\mod F_{n+1}$ of two sides in the Cassini's identity, we get $F^2_n = (-1)^{n+1} \mod F_{n+1}$. But there is a sign ambiguity depending on $n$. I claimed stronger than that one. $\endgroup$ – user530422 Apr 10 '18 at 17:53
  • $\begingroup$ @ToposLogos $3^2\equiv -1 \bmod 5, 5^2\equiv 1 \bmod 8$ and the signs alternate. Likewise $5^2\equiv 1 \bmod 3, 8^2\equiv -1 \bmod 5$ and the signs alternate for that one too. You can't prove that the sign is constant, because it isn't. $\endgroup$ – Mark Bennet Apr 10 '18 at 18:17
0
$\begingroup$

The formulation of the problem is wrong. As it was pointed out in comments, two numbers are needed for this recursion. If it was like you have described it, $F_1 = 2$ and $F_2 = 1$, then $F_3^2 \neq -1 \mod{F_2}$. On the other hand, when $F_1 = 2$ and $F_2 = 2$, then $F_2^2 \neq -1 \mod{F_1}$.

Edit: Maybe the following equality will be helpful (you can use known equalities for Fibonacci numbers):

Let $F_n$ - n-th Fibonacci number, $F'_n$ - n-th modified Fibonacci number (your sequence), then $$F'_{n+1}=F'_n+F'_{n-1}=2F'_{n-1}+F'_{n-2}=3F'_{n-2}+2F'_{n-3}=\dots=F_nF'_{n-(n-2)}+F_{n}F'_{n-(n-1)}=3F_n+2F_{n-1}$$

$\endgroup$

Your Answer

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