ROSS Problem 2

2 (a)

Proof using mathematical induction:

• Base Case: $a_1=F_0{a}_0+F_1{a}_1=0\cdot a_0+1\cdot a_1=a_1$ when $n=1$, holds.
• Induction Assumptions: Assume that the formula holds for $n=k$ and $n=k-1$.
• Induction step:

$$\begin{array}{rl}{a}_{k+1}& =a_k+a_{k-1}\\ & =\left(F_{k-1}{a}_0+F_k{a}_1\right)+\left(F_{k-2}{a}_0+F_{k-1}{a}_1\right)\\ & =(F_{k-1}+F_{k-2})a_0+(F_k+F_{k-1})a_1\\ & =F_k{a}_0+F_{k+1}{a}_1\end{array}$$

Therefore, Eq. holds for all $n\ge 1$.

2 (b)

It is known that $a_4=2a+3a_1=b$, solving for $a_1=\frac{b-2a}{3}$.
and $a_2=a+a_1$ and $a_3=a+2a_1$.
Substituting for $a_1$ gives:

$$a_1=\frac{b-2a}{3},a_2=\frac{a+b}{3},a_3=\frac{2b-a}{3}$$

2 (c)

We need to fulfill the following condition.
$a_1=\frac{b-2a}{3}$ requires $b-2a\equiv 0(\mathrm{mod}3)$
$a_2=\frac{a+b}{3}$ requires $a+b\equiv 0(\mathrm{mod}3)$
$a_3=\frac{2b-a}{3}$ requires $2b-a\equiv 0(\mathrm{mod}3)$

for the first and second conditions:
From $b-2a\equiv 0(\mathrm{mod}3)$ requires $b\equiv 2a(\mathrm{mod}3)$.
From $a+b\equiv 0(\mathrm{mod}3)$ we get $b\equiv -a(\mathrm{mod}3)$.
These two conditions are equivalent because $2a\equiv -a(\mathrm{mod}3)$ holds for any integer $a$.

For the third condition:
When $b\equiv -a(\mathrm{mod}3)$, the substitution $2(-a)-a=-3a\equiv 0(\mathrm{mod}3)$ holds.
So the three conditions can be reduced to $a+b\equiv 0(\mathrm{mod}3)$, i.e., $3\mid (a+b)$.
For all integers a and b it is only necessary to satisfy

$$\boxed{3\mid (a+b)}$$

2 (d)

For positive integers $k$, the integers $a,b$ need to satisfy $F_k\mid (b-F_{k-1}a)$, i.e. $b\equiv F_{k-1}a(\mathrm{mod}{F}_k)$.
For any $n\ge 1$, when $n=k$, substituting the known conditions $a_0=a$ and $a_k=b$, we have:

$$\begin{array}{rl}b& =F_{k-1}a+F_k{a}_1\\ & \\ a_1& =\frac{b-F_{k-1}a}{F_k}\end{array}$$

To ensure that $a_1$ is an integer, $b\equiv F_{k-1}a(\mathrm{mod}{F}_k)$ must be satisfied. In other words there exists an integer $m$ such that $b=F_{k-1}a+F_{k}m$, i.e. $a_1=m$. At this point, the initial terms $a_0=a$ and $a_1=m$ are both integers. According to the recurrence relation $a_n=a_{n-1}+a_{n-2}$, all subsequent terms are sums of integers, so they are all integers.
In summary, all terms of the sequence are integers if and only if $F_k$ divides $(b-F_{k-1}a)$. Therefore, the integers $a,b$ must satisfy:

$$\boxed{F_k\mid (b-F_{k-1}a)}$$

2 (e)

For the extended case of problem (d), given two nonconsecutive terms $a_m$ and $a_n$ ($m<n$), what conditions need to be satisfied to require that all the terms be integers?

According to the conclusion of problem (a), for any $k\ge 0$, there are:

$$a_k=F_{k-1}{a}_0+F_k{a}_1$$

When given $a_m=p$ and $a_n=q$, the joint equation:

$$\{\begin{array}{l}{F}_{m-1}{a}_0+F_m{a}_1=p\\ \\ F_{n-1}{a}_0+F_n{a}_1=q\end{array}$$

The determinant of the above system of equations is:

$$D=\left|\begin{array}{cc}{F}_{m-1}& F_m\\ F_{n-1}& F_n\end{array}\right|=F_{m-1}{F}_n-F_m{F}_{n-1}$$

By the Cassini constant extension of the Fibonacci numbers, $D=(-1{)}^m{F}_{n-m}$. The solution is:

$$a_0=\frac{F_{n}p-F_{m}q}{D},a_1=\frac{F_{n-1}q-F_{m-1}p}{D}$$

For $a_0$ and $a_1$ to be integers, the denominator $D=(-1{)}^m{F}_{n-m}$ must divide the numerator:

• $F_{n-m}\mid (F_{n}p-F_{m}q)$
• $F_{n-m}\mid (F_{n-1}q-F_{m-1}p)$
  Since the Fibonacci numbers satisfy $\gcd (F_k,F_{k+1})=1$ and $\gcd (F_k,F_n)=F_{\gcd (k,n)}$, the conditions can be further simplified.
  By the linear combination property of the Fibonacci numbers, the above integro-division condition is equivalent to:

$$F_{n-m}\mid (p\cdot F_n-q\cdot F_m)$$

If all terms are integers, then $a_0$ and $a_1$ must be integers, so $F_{n-m}$ divides the numerator.
If $F_{n-m}\mid (F_{n}p-F_{m}q)$, then $a_0$ and $a_1$ are integers, and all terms of the recursively generated sequence are integers.
All terms of the f-sequence given the discontinuous terms $a_m=p$ and $a_n=q$ are integers if and only if $F_{n}p-F_{m}q$ is divisible by $F_{n-m}$.

$$\boxed{F_{n-m}\mid (F_{n}p-F_{m}q)}$$