# Show that 5 does not divide L_n

• MHB
• evinda
In summary, the conversation discusses a method for proving that $L_{n+1}+L_{n-1}=5F_n$ for $n \geq 2$ and concluding that $5 \nmid L_n$ for $n \geq 1$. The method involves using induction and considering the cases of $n=1$ and $n\geq 2$. The conversation also addresses some questions and clarifications about the base case and the induction step. Ultimately, it is determined that $5 \nmid L_{n+1}$ holds for all values of $n$.
evinda
Gold Member
MHB
Hello! (Wave)

I want to show that $L_{n+1}+L_{n-1}=5 F_n$ for $n \geq 2$ and conclude that $5 \nmid L_n$ for $n \geq 1$.

I have tried the following:

$L_{n+1}+L_{n-1}=F_n+F_{n+2}+F_{n-2}+F_n=F_n+F_{n+1}+F_n+F_n-F_{n-1}+F_n=4F_n+F_{n+1}-F_{n-1}=4F_n+F_n+F_{n-1}-F_{n-1}=5F_n$.

But how do we deduce that $5 \nmid L_n$ for $n \geq 1$ ? (Thinking)

evinda said:
Hello! (Wave)

I want to show that $L_{n+1}+L_{n-1}=5 F_n$ for $n \geq 2$ and conclude that $5 \nmid L_n$ for $n \geq 1$.

I have tried the following:

$L_{n+1}+L_{n-1}=F_n+F_{n+2}+F_{n-2}+F_n=F_n+F_{n+1}+F_n+F_n-F_{n-1}+F_n=4F_n+F_{n+1}-F_{n-1}=4F_n+F_n+F_{n-1}-F_{n-1}=5F_n$.

But how do we deduce that $5 \nmid L_n$ for $n \geq 1$ ? (Thinking)

Hey evinda!

Suppose 5 does not divide $L_k$ for k up to n, then... (Thinking)

Klaas van Aarsen said:
Hey evinda!

Suppose 5 does not divide $L_k$ for k up to n, then... (Thinking)

So is it right as follows?

Base case: $L_1=1$ and $5 \nmid 1$.

Induction hypothesis: We suppose that $5 \nmid L_k$, $\forall 1 \leq k \leq n$.

Inductive step:$L_{n+1}=5F_n-L_{n-1}$.

Suppose that $5 \mid L_{n+1}$. Then $5 \mid 5F_n-L_{n-1}$ and $5 \mid 5F_n$. So $5 \mid L_{n-1}$, contradiction.
Thus, $5 \nmid L_{n+1}$.

evinda said:
So is it right as follows?

Base case: $L_1=1$ and $5 \nmid 1$.

Induction hypothesis: We suppose that $5 \nmid L_k$, $\forall 1 \leq k \leq n$.

Inductive step:$L_{n+1}=5F_n-L_{n-1}$.

Suppose that $5 \mid L_{n+1}$. Then $5 \mid 5F_n-L_{n-1}$ and $5 \mid 5F_n$. So $5 \mid L_{n-1}$, contradiction.
Thus, $5 \nmid L_{n+1}$.

Suppose we ckeck the inductive step for n=1, aren't we referring to $L_0$ then?
But that is not defined is it? (Worried)6

Klaas van Aarsen said:
Suppose we ckeck the inductive step for n=1, aren't we referring to $L_0$ then?
But that is not defined is it? (Worried)6

So we have to pick $n \geq 2$ ? (Thinking)

evinda said:
So we have to pick $n \geq 2$ ? (Thinking)

Yes. However we will not have proven the statement for $L_2$ will we?
The induction step will cover only $L_3$ and up, and the base case covers only $L_1$. (Sweating)

Klaas van Aarsen said:
Yes. However we will not have proven the statement for $L_2$ will we?
The induction step will cover only $L_3$ and up, and the base case covers only $L_1$. (Sweating)

Do we include at the base case also the case $n=2$ ?

We get that $L_2=3$ and $5 \mid 5$.

We suppose that $5 \nmid L_k$, $\forall 2 \leq k \leq n$.

Then $L_{n+1}=5F_n-L_{n-1}$.

Let $5 \mid L_{n+1}$. Then we get that $5 \mid L_{n-1}$, contradiction.

So $5 \nmid L_{n+1}$.

evinda said:
Do we include at the base case also the case $n=2$ ?

Yes.

evinda said:
We get that $L_2=3$ and $5 \mid 5$.

Shouldn't that be $5 \nmid 3$? (Wondering)

evinda said:
We suppose that $5 \nmid L_k$, $\forall 2 \leq k \leq n$.

Shouldn't that be $\forall 1 \leq k \leq n$ with $n \ge 2$? (Wondering)

evinda said:
Then $L_{n+1}=5F_n-L_{n-1}$.

Let $5 \mid L_{n+1}$. Then we get that $5 \mid L_{n-1}$, contradiction.

So $5 \nmid L_{n+1}$.

Klaas van Aarsen said:
Yes.
Shouldn't that be $5 \nmid 3$? (Wondering)
Shouldn't that be $\forall 1 \leq k \leq n$ with $n \ge 2$? (Wondering)

Nice... (Nod) Thank you! (Happy)

## 1. What does it mean to "divide" a number?

When we say that one number divides another number, it means that the first number can be evenly divided into the second number without leaving any remainder. For example, 3 divides 12 because 12 divided by 3 is equal to 4 with no remainder.

## 2. What is L_n?

L_n refers to the Lucas numbers, which are a sequence of numbers similar to the Fibonacci sequence. They are defined as L_0 = 2, L_1 = 1, and L_n = L_{n-1} + L_{n-2} for n ≥ 2. So, L_n is the nth term in this sequence.

## 3. Why is it important to show that 5 does not divide L_n?

It is important to show that 5 does not divide L_n because it helps us understand more about the properties and patterns of the Lucas numbers. It also has applications in number theory and cryptography.

## 4. How can we prove that 5 does not divide L_n?

We can prove that 5 does not divide L_n by using mathematical induction. First, we can show that 5 does not divide L_0 and L_1. Then, assuming that 5 does not divide L_{n-1} and L_{n-2}, we can show that 5 also does not divide L_n. This will prove that 5 does not divide any term in the Lucas number sequence.

## 5. Can you give an example of a Lucas number that is not divisible by 5?

Yes, L_3 = L_2 + L_1 = 3 + 1 = 4. Since 5 does not divide 4, we can say that 5 does not divide L_3. In fact, the only Lucas numbers that are divisible by 5 are L_0 = 2 and L_1 = 1.

• General Math
Replies
7
Views
2K
• General Math
Replies
1
Views
865
• General Math
Replies
4
Views
2K
• Introductory Physics Homework Help
Replies
41
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
• Calculus and Beyond Homework Help
Replies
4
Views
631
• Calculus
Replies
7
Views
2K
• Mechanical Engineering
Replies
9
Views
1K
• Topology and Analysis
Replies
11
Views
307
• Topology and Analysis
Replies
21
Views
2K