0
$\begingroup$

The Fibonacci sequence can be defined using the recurrence relations:

$F_0 = 0, F_1=1, F_{n} = F_{n-1} + F_{n-2}~~$ for $n \in \mathbb{N} \colon n \geq 2~~~$ (1)

$ F_0 = 0, F_1=1, F_{m+2} = F_m + F_{m+1}~~$ for $m \in \mathbb{N} \colon m \geq 0~~~$ (2)

I believe that these definitions describe the same sequence.

I wish to specify functions in an appropriate mathematical form that specifies the computation of the $i^{th}$ Fibonacci number based on (1) and (2). Are my attempts below reasonable? I am interested in the correct mathematical notation, I already have working computer programs for both cases.

With respect to sequence (1) I think that the following conditional equation is OK.

$ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~fib \colon \mathbb{N} \to \mathbb{N}$ \begin{equation} fib(n)=\begin{cases} 0, & \text{if $n=0$ }\\ 1, & \text{if $n=1$ }\\ fib(n - 1) + fib(n - 2), & \text{if $~n \geq 2$. Assume safe subtraction} \end{cases} \end{equation} Where safe, or truncated, subtraction always result in a natural number $~~\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ \begin{eqnarray} 0 - x = 0 \\ x - 0 = x\\ suc(x) - suc(y) = x - y \end{eqnarray} With respect to sequence (2) I am not too sure. My first attempt is:

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ fib \colon \mathbb{N} \to \mathbb{N}$ \begin{equation} fib(m)=\begin{cases} 0, & \text{if $m=0$ }\\ 1, & \text{if $m=1$ } \end{cases} \end{equation}

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~fib(m + 2) = fib(m) + fib(m +1)$

My problem seems to be that I cannot include the last line within the brace because the condition does not relate solely to $m$.

Edit 1: Maybe it would be better to write the function definition for (2) using multiple equations to specify a piecewise function.

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~fib \colon \mathbb{N} \to \mathbb{N}$

\begin{eqnarray} fib(0) &=& 0\\fib(1) &=& 1\\fib(m + 2) &=& fib(m) + fib(m + 1) \end{eqnarray} The last equation handles cases where $m \geq 2$. The original (2) specifies all case where $m \geq 0$. So I need the two special cases of $m=0$ and $m=1$.

Can these attempts in writing a function for (2) be improved?

Edit 2: Trying to write a function based on sequence (2) using a single conditional equation could give:

$$ fib(m + 2)=\left\{ \begin{array}{rl} 0, & (m+2) = 0\\ 1. & (m+1) = 1\\ fib(m)+fib(m+1), & m \gt 0\\ \end{array}\right. $$ In Edit 2, the Fibonacci numbers are calculated using $fib(m)+fib(m+1)$ from (2) but the condition used are different from (2). I am not sure that the Edit 2 function is actually defined for $m=0$ and $m=1$, because $m$ must be negative for the first two cases. But I think that it is defined for $0,1,2,3,4, \dots$.

Maybe my sequence (1) is not specified correctly with $n\geq 2$, should it be $n\geq 0$? In both cases the sequence is defined from $0 \dots n$ and $0 \dots m$ respectively, with two special cases, but should the condition be $m,n\geq 0$ for both (1) and (2) and the condition $n,m\geq 2$ sould be used in the definition of the functions?

Here is the Haskell code for (2) using Peano arithmetic for plus.

data Nat = Zero | Suc Nat deriving (Eq,Show)

fib Zero = Zero 
fib (Suc Zero) = Suc Zero
fib (Suc (Suc n)) = plus (fib n)  (fib (Suc n))
$\endgroup$
1
  • 3
    $\begingroup$ This is not clear. Of course the two recursions are the same. Just replace the "$n$" in the firs one with "$n+2$" and adjust the range. To write out the second, just use a different letter to avoid confusion. $\endgroup$ – lulu Apr 21 at 11:37
2
$\begingroup$

The numbered conditions are equivalent facts about the sequence, but a definition of the sequence must tell us how to compute $F_n$, and in this respect the two facts (well, two fact statements since they're the same fact) give us the same definition. In Python terms, they both say fib = lambda n: 0 if n==0 else 1 if n==1 else fib(n-1)+fib(n-2) (minus some subtleties we needn't consider such as how to avoid an infinite regress if $n$ isn't a non-negative integer, the fact that this isn't the most efficient computation etc.)

However, there is some value to ($2$) if we rearrange its last equation as $F_n=F_{n+2}-F_{n+1}$, for computing the negative-$n$ cases viz. fib = lambda n: 0 if n==0 else 1 if n==1 else fib(n-1)+fib(n-2) if n>=2 else fib(n+2)-fib(n+1) (again, not worrying about issues such as n needing to be an integer for this to work).

Since you mention pattern matching, suppose we work in a programming language for which n+2 can denote $2$ more than a non-negative integer. Then we can modify my first definition of fib on non-negative integers with a pattern-match that deals with cases other than n==0 and n==1. (This is a more complicated variant of pattern-matching to recursively compute factorials, which only needs the single most recent term.) And again, the rearrangement of (2) would let us use a more complex pattern matching to compute $F_n$ for any integer $n$. I'll leave you to flesh out the details in your favourite language-or-pseudocode syntax.

Edit: in light of the OP's update, I think what's being requested is$$F_{n}=\left\{ \begin{array}{rl} 0 & n=0\\ 1 & n=1\\ F_{n-1}+F_{n-2} & n\ge2\\ F_{n+2}-F_{n+1} & n<0 \end{array}\right..$$

$\endgroup$
4
  • $\begingroup$ @J,G Thanks for the feedback. I have edited the question to focus on the appropriate mathematical notation. $\endgroup$ – Patrick Browne Apr 21 at 19:53
  • 1
    $\begingroup$ @PatrickBrowne Thanks. Does my edit help you? $\endgroup$ – J.G. Apr 21 at 20:10
  • $\begingroup$ Yes it helps. But with the restriction to natural numbers I am not sure that n can be less than zero. $\endgroup$ – Patrick Browne Apr 21 at 22:39
  • 1
    $\begingroup$ @PatrickBrowne Just remove the last row, then. $\endgroup$ – J.G. Apr 22 at 6:06

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.