# How do I write equations for this Fibonacci sequence

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}$$ $$$$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}$$$$ 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}$$ $$$$fib(m)=\begin{cases} 0, & \text{if m=0 }\\ 1, & \text{if m=1 } \end{cases}$$$$

$$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~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))

• 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. – lulu Apr 21 at 11:37

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

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