# Number TheoryShow congruence with Lucas sequence

#### evinda

##### Well-known member
MHB Site Helper
Hello!!!

I want to show that for each $n \geq 1$ it holds that $2^n L_n \equiv 2 \pmod{10}$.

$L_n$ is the Lucas sequence.

According to my notes,

$$L_n=\left( \frac{1+\sqrt{5}}{2}\right)^n+\left( \frac{1-\sqrt{5}}{2}\right)^n$$

and
$$L_n=F_{n-1}+F_{n+1},$$

where $F_n$ is the $n$-th Fibonacci number.

Could you give me a hint how we get the desired congruence?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Hello!!!

I want to show that for each $n \geq 1$ it holds that $2^n L_n \equiv 2 \pmod{10}$.

$L_n$ is the Lucas sequence.

According to my notes,

$$L_n=\left( \frac{1+\sqrt{5}}{2}\right)^n+\left( \frac{1-\sqrt{5}}{2}\right)^n$$

and
$$L_n=F_{n-1}+F_{n+1},$$

where $F_n$ is the $n$-th Fibonacci number.

Could you give me a hint how we get the desired congruence?
Hey evinda !!

Don't we have $L_n = L_{n-1} + L_{n-2}$?
Perhaps we can apply induction?

#### evinda

##### Well-known member
MHB Site Helper
Hey evinda !!

Don't we have $L_n = L_{n-1} + L_{n-2}$?
Perhaps we can apply induction?
Since $L_n=F_{n-1}+F_{n+1}$, does it hold that $L_n$ is only defined for $n \geq 2$ ?

Also, we have that $L_2=F_1+F_3=1+F_1+F_2=3$.

For $n=2$: $2^n L_n=2^2 L_2= 4 \cdot 3=12 \equiv 2 \pmod{10}$.

Then we suppose that $2^k L_k \equiv 2 \pmod{10}$.

Then $2^{k+1} L_{k+1}=2 \cdot 2^k (L_k+L_{k+2})$.

Is it right so far? If so, how can we continue?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Since $L_n=F_{n-1}+F_{n+1}$, does it hold that $L_n$ is only defined for $n \geq 2$ ?
Wiki says here:
The Lucas numbers may thus be defined as follows:
$$L_n := \begin{cases} 2 & \text{if } n = 0; \\ 1 & \text{if } n = 1; \\ L_{n-1}+L_{n-2} & \text{if } n > 1. \\ \end{cases}$$​

Isn't that consistent with your definition?

Usually $F_0=0, F_1=1, F_2=1, F_3=2$.
It follows that $L_1=1, L_2=3$, and we can choose to define $L_0=2$.

Also, we have that $L_2=F_1+F_3=1+F_1+F_2=3$.

For $n=2$: $2^n L_n=2^2 L_2= 4 \cdot 3=12 \equiv 2 \pmod{10}$.

Then we suppose that $2^k L_k \equiv 2 \pmod{10}$.

Then $2^{k+1} L_{k+1}=2 \cdot 2^k (L_k+L_{k+2})$.

Is it right so far? If so, how can we continue?
Shouldn't that be: $2^{k+1} L_{k+1}=2 \cdot 2^k (L_{k}+L_{k-1})$ ?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Note that:
$$L_{n-1}+L_{n-2}=(F_{n-2}+F_n)+(F_{n-3}+F_{n-1})=(F_{n-3}+F_{n-2})+(F_{n-1}+F_{n})=F_{n-1}+F_{n+1}=L_n$$

And we basically need to have a proper recursive definition of $L_n$ to apply induction.

#### Opalg

##### MHB Oldtimer
Staff member
Hello!!!

I want to show that for each $n \geq 1$ it holds that $2^n L_n \equiv 2 \pmod{10}$.

$L_n$ is the Lucas sequence.

According to my notes,

$$L_n=\left( \frac{1+\sqrt{5}}{2}\right)^n+\left( \frac{1-\sqrt{5}}{2}\right)^n$$

and
$$L_n=F_{n-1}+F_{n+1},$$

where $F_n$ is the $n$-th Fibonacci number.

Could you give me a hint how we get the desired congruence?
Another approach would be to start from the definition $L_n=\left( \frac{1+\sqrt{5}}{2}\right)^n+\left( \frac{1-\sqrt{5}}{2}\right)^n$. So $2^nL_n=(1+\sqrt{5})^n+(1-\sqrt{5})^n$. Now form the binomial expansions: $\textstyle \bigl(1 + {n\choose1}\sqrt5 + {n\choose2}5 + \ldots\bigl)\ +\ \bigl(1 - {n\choose1}\sqrt5 + {n\choose2}5 + \ldots\bigl)$ When you add the two series, the first term is $2$, the odd-numbered terms (involving $\sqrt5$) all cancel, and the remaining terms are all multiples of $2$ and of $5$.

#### evinda

##### Well-known member
MHB Site Helper
Another approach would be to start from the definition $L_n=\left( \frac{1+\sqrt{5}}{2}\right)^n+\left( \frac{1-\sqrt{5}}{2}\right)^n$. So $2^nL_n=(1+\sqrt{5})^n+(1-\sqrt{5})^n$. Now form the binomial expansions: $\textstyle \bigl(1 + {n\choose1}\sqrt5 + {n\choose2}5 + \ldots\bigl)\ +\ \bigl(1 - {n\choose1}\sqrt5 + {n\choose2}5 + \ldots\bigl)$ When you add the two series, the first term is $2$, the odd-numbered terms (involving $\sqrt5$) all cancel, and the remaining terms are all multiples of $2$ and of $5$.
Ah, I see... Thank you...

- - - Updated - - -

Note that:
$$L_{n-1}+L_{n-2}=(F_{n-2}+F_n)+(F_{n-3}+F_{n-1})=(F_{n-3}+F_{n-2})+(F_{n-1}+F_{n})=F_{n-1}+F_{n+1}=L_n$$

And we basically need to have a proper recursive definition of $L_n$ to apply induction.
We cannot use this property because it contains both $L_{n-1}$ and $L_{n-2}$... Or am I wrong?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
We cannot use this property because it contains both $L_{n-1}$ and $L_{n-2}$... Or am I wrong?
It's the proof that $L_n=L_{n-1} + L_{n-2}$.
This proof uses only the definition for the Lucas numbers in post #1, doesn't it?