Show congruence with Lucas sequence

[evinda]

Hello! (Wave)

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? (Thinking)

 

[I like Serena]

Hello! (Wave)

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? (Thinking)

Hey evinda!

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

 

[evinda]

Hey evinda!

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

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? (Thinking)

 

[I like Serena]

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

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})$ ? (Wondering)

 

[I like Serena]

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. (Thinking)

 

[Opalg]

Hello! (Wave)

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? (Thinking)

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]

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... (Smile)

- - - 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. (Thinking)

We cannot use this property because it contains both $L_{n-1}$ and $L_{n-2}$... Or am I wrong?

 

[I like Serena]

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? (Wondering)