The fibonacci sequence is defined as x0 = 0, x1 = 1 and xn+2 = xn +xn+1 , for all non negative integers n prove that, xm = xr+1xm-r + xrxm-r for all integers m ≥ 1 and 0 ≤ r ≤ m-1 and xd divides xkd for all integers k and d

1.

$x_m=x_{r+1}x_{m-r}+x_rx_{m-r}$

Prove by the induction

$x_m=x_{m-r}x_{r+2} \ \ \ \ \ \ \ \ \ \ \ \ (*)$

Since $m\geq1$ the base of induction is:

$m=1=>r=0: x_1=x_{1-0}x_{0+2}=1\cdot1=1$

Hence, we proved the base of induction.

Now, we will assume, that the statement (*) is true for every $m<k.$ Let's prove for $m=k$

Prove by the induction (by r)

$r=0$

$x_k=x_{k-0}x_{0+2} =x_kx_2=x_k$

The induction assumption is that for every $r,$ such that: $0\leq r<r_0\leq k-1,$ the statement (*) is true. Let's prove it for $r=r_0.$ We should check the following:

$x_k=x_{k-r_0}x_{r_0+2}=x_{k-r_0}x_{r_0+1}+x_{k-r_0}x_{r_0}$

We can apply the induction assumption to both of the summands in the following way:

For the first summand:

$r_0+1=(r_0-1)+2, k-r_0=(k-1)-(r_0-1)$

We obtain the following(by using the (*)): 

$x_{k-r_0}x_{r_0+1}=x_{k-1}$

By applying the induction assumption and (*) to the second summand we obtain: 

$x_{k-r_0}x_{r_0}=x_{k-2}$

Thus we should check if:

$x_k=x_{k-1}+x_{k-2}$

This is true.

$x_m=x_{m-r}x_{r+2}=x_{m-r}(x_{r+1}+x_r)=x_{m-r}x_{r+1}+x_{m-r}x_r$

We prove

$x_m=x_{r+1}x_{m-r}+x_rx_{m-r}$

2.

$x_k|x_{kd},$ where $k,d$ are some integers.

Let's use the statement:

$x_m=x_{m-r}x_{r+2}$$x_{kd}=x_{kd-d}x_{d+2}$

By applying this fact $(k-1)$ times, we obtain the following: 

$x_{kd} = x_{d} x_{d+2}^{k-1}.$

Thus $(k\geq1): x_k|x_{kd},$ where $k,d$ are some integers.