Prove That If $a$ Divides Fibonacci $F_n$ For Every $d \geq 1$

  • MHB
  • Thread starter Grupax
  • Start date
In summary, we can use the formula and property stated to prove that if $a \geq 2$ divides the nth Fibonacci number, then for every $d \geq 1$, $a^{d}$ divides $F_{a^{d-1}n}$, by using induction and choosing appropriate values for $k$ and $n$ in the formula.
  • #1
Grupax
1
0
let $F_{n}$ the nth fibonacci number. Prove that if $a \geq 2$ divide $F_{n}$ then for every $d \geq 1$ we have $$a^{d}\mid F_{a^{d-1}n}.$$ I think we can use the formula $$F_{kn}= \underset{i=1}{\overset{k}{\sum}} \dbinom{k}{i}F_{i}F_{n}^{i}F_{n-1}^{k-i}$$ and the well know property that if $b \mid c$ then $F_{b} \mid F_{c}$ but I haven't find the solution yet.
 
Mathematics news on Phys.org
  • #2
Yes, you are right indeed, it follows from $
F_{k\,n} = \sum_{j=1}^k \binom{k}{j} F_j\, F_n^j F_{n-1}^{k-j}
$ and inductive reasoning.

Simply pick $k := a$, $ n := a^{d-1}\,n$ in that equation above, then observe that $F_{a^{d-1}\,n}^j$ is a multiple of $a^{d+1}$ for $j\geq 2$ (use the inductive hypothesis here), while, for $j = 1$, we have $\binom{a}{1} = a$ and $a^{d} | F_{a^{d-1}\,n}$. This proves that if $a^d | F_{a^{d-1}\,n}$, then $a^{d+1} | F_{a^d\,n}$.
 

FAQ: Prove That If $a$ Divides Fibonacci $F_n$ For Every $d \geq 1$

How is the relationship between $a$ and Fibonacci numbers defined?

The relationship between $a$ and Fibonacci numbers is defined as follows: if $a$ divides $F_n$ for every $d \geq 1$, then $a$ is said to be a divisor of Fibonacci numbers.

Can you provide an example of $a$ dividing Fibonacci numbers?

Sure, for example, if $a=3$, then $3$ is a divisor of Fibonacci numbers because $3$ divides $F_n$ for every $n \geq 1$. This is because the Fibonacci sequence is defined recursively as $F_n = F_{n-1} + F_{n-2}$, so each term is the sum of the two previous terms, making it divisible by $3$.

What is the significance of $d \geq 1$ in the statement?

The statement $a$ divides Fibonacci $F_n$ for every $d \geq 1$ means that the divisibility holds for all terms of the Fibonacci sequence, starting from the first term ($n=1$) and continuing indefinitely. This is important because it shows that the divisibility holds for all possible values of $n$, not just a specific subset.

Is it possible for $a$ to divide Fibonacci numbers for some values of $d$ but not others?

No, if $a$ is a divisor of Fibonacci numbers, then it must divide every term in the sequence. This is because the divisibility is defined for all $d \geq 1$, so if $a$ does not divide a certain term, it will not hold for all values of $d$.

How does this property of $a$ dividing Fibonacci numbers relate to the overall pattern of the sequence?

This property is related to the fact that the Fibonacci sequence exhibits a specific pattern based on the previous terms, making it predictable and allowing for the divisibility by $a$. This can also be seen in the closed form expression for the Fibonacci sequence, $F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}$, where $\varphi$ and $\psi$ are the roots of the characteristic equation $x^2-x-1=0$, and any divisor of $F_n$ must also divide the numerator.

Similar threads

Replies
8
Views
2K
Replies
7
Views
2K
Replies
11
Views
857
Replies
3
Views
2K
Back
Top