Let $F_0, F_1, F_2, \ldots$ be the Fibonacci numbers, defined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for all $n\geq 2$.

In [this][1] question Oleg567 conjectured the following interesting fact about Fibonacci numbers:
$$ k\mid F_n\quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n} $$
where $k \in \mathbb{N}$ and $n \in \mathbb{N}$.
This can be regarded as an analogue of Hensel's lifting lemma.

I would be glad to give a proof (following the share your knowledge, Q&A-style), based on a simple combinatorial identity, and see if others come out with more elegant ones.


 [1]: http://math.stackexchange.com/questions/872071/fibonacci-number-that-ends-with-2014-zeros/872077#872077