# Show congruence with Lucas sequence

• MHB
• evinda
In summary, the conversation is about proving the congruence $2^n L_n \equiv 2 \pmod{10}$ for the Lucas sequence $L_n$. The conversation discusses different approaches and definitions of the Lucas sequence and how to use induction to prove the congruence. One approach involves starting from the definition of $L_n$ and using binomial expansions, while another approach involves using the property $L_n = L_{n-1} + L_{n-2}$ and a proper recursive definition of $L_n$.
evinda
Gold Member
MHB
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)

evinda said:
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)

Klaas van Aarsen said:
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)

evinda said:
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)

evinda said:
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)

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)

evinda said:
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$.

Opalg said:
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 - - -

Klaas van Aarsen said:
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?

evinda said:
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)

## 1. What is a Lucas sequence?

A Lucas sequence is a sequence of numbers where each term is the sum of the two preceding terms, similar to the Fibonacci sequence. It is named after the mathematician Édouard Lucas.

## 2. How is the Lucas sequence related to other mathematical concepts?

The Lucas sequence is closely related to the Fibonacci sequence, as both are examples of linear recurrence relations. It can also be used in the study of number theory, particularly in relation to prime numbers.

## 3. What is the formula for finding the nth term in a Lucas sequence?

The formula for finding the nth term in a Lucas sequence is: Ln = φ^n + (1-φ)^n, where φ is the golden ratio (approximately 1.618) and n is the term number.

## 4. How can the Lucas sequence be used in real-world applications?

The Lucas sequence has been applied in various fields such as finance, computer science, and biology. For example, it can be used to model population growth or in the development of efficient algorithms.

## 5. Is the Lucas sequence a finite or infinite sequence?

The Lucas sequence is an infinite sequence, as it continues infinitely with no repeating pattern. However, in practical applications, a finite number of terms may be used for calculation purposes.

Replies
8
Views
2K
Replies
4
Views
1K
Replies
1
Views
2K
Replies
1
Views
1K
Replies
2
Views
1K
Replies
2
Views
4K
Replies
21
Views
3K
Replies
1
Views
2K
Replies
4
Views
3K
Replies
3
Views
2K