Answer to Question #113232 in Discrete Mathematics for aa

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}.$

Let's simplify this statement:

$x_m=x_{r+1}x_{m-r} + x_rx_{m-r} = x_{m-r}(x_{r+1} + x_r) = x_{m-r}x_{r+2}$ (*). Let's prove it using the induction by r and m simultaneously. Let's prove it for every m(so m is fixed).

Since $m\ge 1$ , the base of induction is:

$m=1: x_1 = x_{1-r}x_{r+2}.$ Since $0 \le r \le m-1$, we obtain that $r = 0$ . Thus, we should check if$x_1 = x_{1-0}x_{0+2} = 1\cdot 1 = 1$ . Hence, we proved the base of induction.

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

Let's prove the base of induction(by r):

a) $r =0.$ Hence, we should check if: $x_{m_0} = x_{m_0 -0}x_{0+2} = x_{m_0}x_2 = x_{m_0}.$

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

$x_{m_0} = x_{m_0 - r_0}x_{r_0 +2} = x_{m_0 - r_0}x_{r_0 +1} + x_{m_0 - 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, m_0 -r_0 = (m_0 -1) - (r_0 -1)$ , and we obtain the following(by using the (*)): $x_{m_0 - r_0}x_{r_0 +1} = x_{m_0 -1}$. By applying the induction assumption and (*) to the second summand we obtain: $x_{m_0 - r_0}x_{r_0} = x_{m_0 -2}.$ Thus we should check if: $x_{m_0} = x_{m_0 -1} + x_{m_0 -2}.$ This is true.

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

Let's use the previous statement:

$x_{kd} = x_{kd -d }x_{d+2} = x_{(k-1)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 \ge 1)$ : $x_d |x_{kd}$