Problem 1547

To show that $F_{mn-1} - F_{n-1}^m$ is divisible by $F_n^2$ for all $m \ge 1$ and $n > 1$, we will use induction on $m$.

1. **Base Case: $m = 1$**

For $m = 1$, we need to show that $F_n^2 \mid F_{n-1} - F_{n-1}$.

$$F_{n-1} - F_{n-1} = 0$$

Clearly, $F_n^2 \mid 0$. Thus, the base case holds.

2. Inductive Step:

Assume that the statement holds for $m = k$, i.e.,

$$F_n^2 \mid F_{kn-1} - F_{n-1}^k$$

We need to show that the statement holds for $m = k+1$, i.e.,

$$F_n^2 \mid F_{(k+1)n-1} - F_{n-1}^{k+1}$$

Using the property of Fibonacci numbers $F_{a+b} = F_a F_{b+1} + F_{a-1} F_b$, we can write:

$$F_{(k+1)n-1} = F_{kn+n-1} = F_{kn-1} F_{n+1} + F_{kn-2} F_n$$

By the induction hypothesis, we know that $F_n^2 \mid F_{kn-1} - F_{n-1}^k$. Therefore, we can write:

$$F_{kn-1} \equiv F_{n-1}^k \pmod{F_n^2}$$

Substituting this into the expression for $F_{(k+1)n-1}$:

$$F_{(k+1)n-1} = F_{kn-1} F_{n+1} + F_{kn-2} F_n$$

$$\equiv F_{n-1}^k F_{n+1} + F_{kn-2} F_n \pmod{F_n^2}$$

We also know that $F_{kn-2} \equiv F_{kn} - F_{kn-1} \pmod{F_n}$. Since $F_n \mid F_{kn}$, we have:

$$F_{kn-2} \equiv -F_{kn-1} \pmod{F_n}$$

Substituting this back, we get:

$$F_{(k+1)n-1} \equiv F_{n-1}^k F_{n+1} - F_{n-1}^k F_n \pmod{F_n^2}$$

$$\equiv F_{n-1}^k (F_{n+1} - F_n) \pmod{F_n^2}$$

Using the identity $F_{n+1} = F_n + F_{n-1}$, we get:

$$F_{(k+1)n-1} \equiv F_{n-1}^k (F_n + F_{n-1} - F_n) \pmod{F_n^2}$$

$$\equiv F_{n-1}^k F_{n-1} \pmod{F_n^2}$$

$$\equiv F_{n-1}^{k+1} \pmod{F_n^2}$$

Therefore,

$$F_n^2 \mid F_{(k+1)n-1} - F_{n-1}^{k+1}$$

This completes the inductive step.

By induction, we have shown that $F_{mn-1} - F_{n-1}^m$ is divisible by $F_n^2$ for all $m \ge 1$ and $n > 1$.

$\blacksquare$