0
$\begingroup$

Consider the graph $P_3$ : $n_1$ \rightarrow$ $n_2$\rightarrow$ $n_3\rightarrow$ $n_4$

we count 6 paths of length k=1, namely:

$n_1$ $\rightarrow$ $n_2$

$n_2$ $\rightarrow$ $n_3$

$n_3\rightarrow$ $n_4$

$n_4\rightarrow$ $n_3$

$n_3\rightarrow$ $n_2$

we count 10 for k=2, and we define the Fibonacci sequence $f$ for k $\geqslant$ 3:

$f_1$ = 6, $f_2$ = 10

$f_k$ := $f_{k-1}$ + $f_{k-2}$

with that we see that $f_3$ = 16, $f_4$ = 26, $f_5$ = 42, etc

... that's as far as i've gotten and now i'm stuck.

2 Answers 2

1

Since it is not clear to me that anyone has proved that if $u_k$ is the number of paths of length $k$ then $u_k=u_{k-1}+u_{k-2}$, I'll post a proof.

I prefer to call the four points $A,B,C,D$ in order from left to right. Let $a_k$ be the number of paths of length $k$ starting at $A$, similarly for $b_k,c_k,d_k$. The following relations hold: $u_k=a_k+b_k+c_k+d_k\tag1$ since every path has to start somewhere; $a_k=d_k,\qquad b_k=c_k\tag2$ by symmetry; $a_k=b_{k-1}\tag3$ since every path that starts at $A$ must start by going to $B$; $b_k=a_{k-1}+c_{k-1}\tag4$ since every path that starts at $B$ must start by going to either $A$ or $C$. From (2) and (4) we get $b_k=a_{k-1}+b_{k-1}\tag5$ From (3) and (5) we get $b_k=b_{k-1}+b_{k-2}\tag6$ From (3) and (6) we get $a_k=a_{k-1}+a_{k-2}\tag7$ From (2), (6), and (7) we get $c_k=c_{k-1}+c_{k-2},\qquad d_k=d_{k-1}+d_{k-2}\tag8$ From (1), (6), (7), and (8) we finally get $u_k=u_{k-1}+u_{k-2}\tag9$

The rest of the problem is done in the answer by Cocopuffs and the comments on it, but for completeness sake I'll write it up independently here.

The Fibonacci sequence is usually defined by $F_1=1,\quad F_2=1,\quad F_k=F_{k-1}+F_{k-2}\tag{10}$ We see that $u_1=6=2F_4,\quad u_2=10=2F_5\tag{11}$ Since $u_k$ and $F_k$ satisfy the same recurrence it follows (by induction, if you want) that $u_k=2F_{k+3}\tag{12}$ for all $k$.

1

Since you have $f_k = f_{k-1} + f_{k-2}$, you've got the induction part finished - all that's left is to describe $f_k$ in terms of the Fibonacci numbers $F_k$ defined by

$F_1 = 1$, $F_2 = 2$, $F_k = F_{k-1} + F_{k-2}$.

The set of sequences $(f_k)_{k \ge 0}$ satisfying $f_k = f_{k-1} + f_{k-2}$ for $k \ge 3$ is a real vector space: you can see quickly that it's closed under addition and scalar multiplication. Since each sequence is determined by its first two components, its dimension is two.

What this means is that given two linearly independent starting values

(for example, $F_1 = 1$, $F_2 = 2$ and $G_1 = 2$, $G_2 = 3$, so $G_k = F_{k+1}$) you can write your $f_k$ as a linear combination of the two.

So we need to represent $\begin{pmatrix} 6 \\ 10 \end{pmatrix} = \lambda \begin{pmatrix} 1 \\ 2 \end{pmatrix} + \mu \begin{pmatrix} 2 \\ 3 \end{pmatrix} $ with $\lambda, \mu \in \mathbb{R}$. You can find that $\lambda = 2$ and $\mu = 2$,

which gives you $f_k = 2F_k + 2F_{k+1} = 2F_{k+2}$.

  • 0
    nearly there, we've ran the numbers and found that it's $f_k = 2F_{k+3}$. could this be true or are we missing something ?2012-06-21