0
$\begingroup$

Under what conditions does $F_z = a F_x + b F_y$ imply $F_{z+k} = a F_{x+k} + b F_{y+k}$?

For example, $F_4 = 3 F_2 - F_0$, and $F_5 = 3 F_3 - F_1$, $F_6 = 3 F_4 - F_2$, etc.

If I can prove using the matrix form $$A^n =\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$$

that

$$A^z = a A^x + b A^y $$

then I can simply multiply by $A$.

$\endgroup$
  • 1
    $\begingroup$ In saying $F_z = a F_x + b F_y$ you kinda have to relate $z$, $x$ and $y$ somehow or this is not true at all. For what $x,y,z$ is this true? For all of them? For just the $z=x+y$ ones? For $x-y$ a constant? $\endgroup$ – vrugtehagel Aug 23 '18 at 2:08
  • $\begingroup$ @vrugtehagel I found values of $a,b,x,y,z$ such that this is true. Another example is $F_3 = 2 F_2 - F_0$ which seems to hold for any $k$. $\endgroup$ – qwr Aug 23 '18 at 2:13
  • $\begingroup$ @vrugtehagel these specifically math.stackexchange.com/q/2806811/122489 $\endgroup$ – qwr Aug 23 '18 at 2:16
  • $\begingroup$ Well from just $F_3=2F_2-F_0$ you can't prove $F_4=2F_3-F_1$ because you didn't define any recursion, you just linked three constants $F_3,F_2,F_0$ by some equation. $\endgroup$ – vrugtehagel Aug 23 '18 at 2:57
1
$\begingroup$

First some background-

  • Equation - A relation between algebraic quantities (variables) which may be true for none, some or all values of the variables.

  • Identity - A equation that is true for all values of the variables.


The relation-

Now, $F(2) \neq 2. F(3) + F(89)$ (for example), so that the relation is not an identity but simply an equation that can be solved to get values of $a$, $b$, $x$, $y$ and $z$ ( although it probably had no closed form solution ).


A counter example-

$F(4) = 2. F(1) + F(2)$

But, $F(5) \neq 2. F(2) + F(3)$

Therefore, the implication does not always hold and we need to find some condition(s) for which it holds.


An example relation (to get us on the right track)-

One such solution can be -

$$F(n) = 4. F(n-3) + F(n-6)$$

Obviously, the question of a proof by induction does not arise, as there is no recursive relation to use.

Note that, $F(n+k)$ is necessarily equal to $4.F(n-3+k) + F(n-6+k)$.

PROOF-

Our claim is -

Claim-

Given, $F(n) = 4.F(n-3) + F(n-6), \ \forall \ n\ \gt 6 in \mathbb{N}$

we have $S(k) := F(n + k) = 4.F(n-3+k) + F(n-6+k),$ is true $ \forall \ k \in \mathbb{N}$ .

Solution-

First, the base cases -

$S(0)$ is true by hypothesis.

Also, $S(1)$ is true-

$F(n+1)=4.F(n-3+1)+ F(n-6+1)$

$\Leftrightarrow \ F((n+1)) = 4. F((n+1) - 3)+F((n+1)-6)$ (The result is true for all natural $n>6$, but $n+1$ is also a natural number)

Now, it is trivial to see that -

$F(n+k)=4.F(n-3+k)+ F(n-6+k)$

$\Leftrightarrow \ F((n+k)) = 4. F((n+k) - 3)+F((n+k)-6)$

Basically, we already know the relation to be true for every natural number above 6, so the addition by $k$ can be reinterpreted as an stating the relation for the $k^(th)$ natural number after it, which is again true, since relation is true for each and every natural number (greater than 6).

We, can do the proof by mathematical induction if we want a feeling of greater rigor; but this proof is also perfectly valid and rigorous.


The final answer-

The above proof, suggests one condition which guarantees the property you want -

$$F(x) = a.F(y) + b.F(z) \Rightarrow F(x+k) = a. F(y+k) + b. F(z+k)$$

if $y$ and $z$ are linear functions of $x$ with coefficient of x being 1.

(Note the use of if as opposed to iff.)

That is, if an increment in $x$ automatically leads to an equal increment in $y$ and $z$.

The proof for this condition is exactly the same as the one above ( and is left to the reader :P ).

This may not necessarily be the only such condition (hence, if instead of iff), but I am unable to prove that either way.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But $F_{n+k} = 4 F_{n-3+k} + F_{n-6+k}$. It is proved when $k$ is a multiple of $n$ here math.stackexchange.com/q/2806811/122489 $\endgroup$ – qwr Aug 23 '18 at 4:25
  • $\begingroup$ Are you sure? I believe it holds for all $k$ I just can't prove it. $\endgroup$ – qwr Aug 23 '18 at 5:14
  • $\begingroup$ Adding the multiplicity condition would ean that that the formula is essentially unchanged. No doubt, that is part of (or at least, close to) the central idea in recurrence relations, but the idea I was trying to get across was that there is nothing to be proved in the formula as it stands. $\endgroup$ – Devashsih Kaushik Aug 23 '18 at 5:16
  • $\begingroup$ The question that you linked to asks for the values that the coefficients (Here, $a$ and $b$) would take. Similarily, you would first need to decide what your boundary conditions are before attempting a proof. (Basically, the meaning of the relation is still unclear. ) $\endgroup$ – Devashsih Kaushik Aug 23 '18 at 5:20
  • $\begingroup$ @qwr Ok, you are correct about this case. I will add the proof. Just let me check the general case again. $\endgroup$ – Devashsih Kaushik Aug 23 '18 at 5:25
0
$\begingroup$

I can check by hand \begin{align} F_{z} & = a F_{x} + b F_{y} \\ F_{z+1} & = a F_{x+1} + b F_{y+1} \\ \end{align}

then add the equations.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "You can check by hand"? You mean, "I assume"? There's nothing you can prove that with. The relation for $x,y,z$ isn't even mentioned $\endgroup$ – vrugtehagel Aug 26 '18 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.