Skip to main content
MathOverflow

Return to Question

added 394 characters in body
Source Link
Voile
Voile
  • 131
  • 3

Many years ago, I saw the following Fibonacci identity from somewhere online, without proof:

Let usual $F(n)$ be Fibonacci numbers with $F(0) = 0, F(1) = 1$, then we have

$$F(n) = \left(p ^ {n + 1} \bmod \left(p ^ 2 - p - 1\right)\right) \bmod p$$

where $p = 2 ^ {n + 1}$.

I couldn't find the source anymore, and it wouldn't help anyway as it didn't contain a proof. As far as I looked around Google search results this is not documented anywhere notable (e.g Wikipedia or here); Fibonacci identities with modulo are usually discussed under the topic of Pisano period, and never contains 2 modulo. However, it looks like it has something to do with the generating function.

Is there a proof for this identity, or are there any existing material where this identity is mentioned/proved?

Edit

There is a write-up on a very similar identity here, proven using generating function:

$$ F(n) = \left\lfloor\frac{p ^ {n + 1}} {p ^ 2 - p - 1}\right\rfloor \bmod p $$

They look almost the same but can't be more different! One is the quotient and one is the modulo. I'm not even sure if they are related to each other.

Many years ago, I saw the following Fibonacci identity from somewhere online, without proof:

Let usual $F(n)$ be Fibonacci numbers with $F(0) = 0, F(1) = 1$, then we have

$$F(n) = \left(p ^ {n + 1} \bmod \left(p ^ 2 - p - 1\right)\right) \bmod p$$

where $p = 2 ^ {n + 1}$.

I couldn't find the source anymore, and it wouldn't help anyway as it didn't contain a proof. As far as I looked around Google search results this is not documented anywhere notable (e.g Wikipedia or here); Fibonacci identities with modulo are usually discussed under the topic of Pisano period, and never contains 2 modulo. However, it looks like it has something to do with the generating function.

Is there a proof for this identity, or are there any existing material where this identity is mentioned/proved?

Many years ago, I saw the following Fibonacci identity from somewhere online, without proof:

Let usual $F(n)$ be Fibonacci numbers with $F(0) = 0, F(1) = 1$, then we have

$$F(n) = \left(p ^ {n + 1} \bmod \left(p ^ 2 - p - 1\right)\right) \bmod p$$

where $p = 2 ^ {n + 1}$.

I couldn't find the source anymore, and it wouldn't help anyway as it didn't contain a proof. As far as I looked around Google search results this is not documented anywhere notable (e.g Wikipedia or here); Fibonacci identities with modulo are usually discussed under the topic of Pisano period, and never contains 2 modulo. However, it looks like it has something to do with the generating function.

Is there a proof for this identity, or are there any existing material where this identity is mentioned/proved?

Edit

There is a write-up on a very similar identity here, proven using generating function:

$$ F(n) = \left\lfloor\frac{p ^ {n + 1}} {p ^ 2 - p - 1}\right\rfloor \bmod p $$

They look almost the same but can't be more different! One is the quotient and one is the modulo. I'm not even sure if they are related to each other.

added 9 characters in body
Source Link
Voile
Voile
  • 131
  • 3

Many years ago, I saw the following Fibonacci identity from somewhere online, without proof:

Let usual $F(n)$ be Fibonacci numbers with $F(0) = 0, F(1) = 1$, then we have

$$F(n) \equiv p ^ {n + 1} \bmod \left(p ^ 2 - p - 1\right) \mod p$$$$F(n) = \left(p ^ {n + 1} \bmod \left(p ^ 2 - p - 1\right)\right) \bmod p$$

where $p = 2 ^ {n + 1}$.

I couldn't find the source anymore, and it wouldn't help anyway as it didn't contain a proof. As far as I looked around Google search results this is not documented anywhere notable (e.g Wikipedia or here); Fibonacci identities with modulo are usually discussed under the topic of Pisano period, and never contains 2 modulo. However, it looks like it has something to do with the generating function.

Is there a proof for this identity, or are there any existing material where this identity is mentioned/proved?

Many years ago, I saw the following Fibonacci identity from somewhere online, without proof:

Let usual $F(n)$ be Fibonacci numbers with $F(0) = 0, F(1) = 1$, then we have

$$F(n) \equiv p ^ {n + 1} \bmod \left(p ^ 2 - p - 1\right) \mod p$$

where $p = 2 ^ {n + 1}$.

I couldn't find the source anymore, and it wouldn't help anyway as it didn't contain a proof. As far as I looked around Google search results this is not documented anywhere notable (e.g Wikipedia or here); Fibonacci identities with modulo are usually discussed under the topic of Pisano period, and never contains 2 modulo. However, it looks like it has something to do with the generating function.

Is there a proof for this identity, or are there any existing material where this identity is mentioned/proved?

Many years ago, I saw the following Fibonacci identity from somewhere online, without proof:

Let usual $F(n)$ be Fibonacci numbers with $F(0) = 0, F(1) = 1$, then we have

$$F(n) = \left(p ^ {n + 1} \bmod \left(p ^ 2 - p - 1\right)\right) \bmod p$$

where $p = 2 ^ {n + 1}$.

I couldn't find the source anymore, and it wouldn't help anyway as it didn't contain a proof. As far as I looked around Google search results this is not documented anywhere notable (e.g Wikipedia or here); Fibonacci identities with modulo are usually discussed under the topic of Pisano period, and never contains 2 modulo. However, it looks like it has something to do with the generating function.

Is there a proof for this identity, or are there any existing material where this identity is mentioned/proved?

Source Link
Voile
Voile
  • 131
  • 3

Proof of an unknown source Fibonacci identity with double modulo

Many years ago, I saw the following Fibonacci identity from somewhere online, without proof:

Let usual $F(n)$ be Fibonacci numbers with $F(0) = 0, F(1) = 1$, then we have

$$F(n) \equiv p ^ {n + 1} \bmod \left(p ^ 2 - p - 1\right) \mod p$$

where $p = 2 ^ {n + 1}$.

I couldn't find the source anymore, and it wouldn't help anyway as it didn't contain a proof. As far as I looked around Google search results this is not documented anywhere notable (e.g Wikipedia or here); Fibonacci identities with modulo are usually discussed under the topic of Pisano period, and never contains 2 modulo. However, it looks like it has something to do with the generating function.

Is there a proof for this identity, or are there any existing material where this identity is mentioned/proved?