Answer to Question #113275 in Discrete Mathematics for Tayyaba

Question

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

Answer 1

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.