Close Menu Navigation

# The Fib-Fib-Fib Sequence

Consider the sequences , defined recursively by

Show that

## Table Of Content

1. Show that

Show that

Show that

Yeah, I’m getting a bit sick of these sequence problems too…

### 1. Show that

Let’s start with the sequence first. We use the following code to generate .

b_ = {}
def b(n):
if n in b_:
return b_[n]
x = a(n-1) - b(n-1) + b(n-2)
b_[n] = x
return x

Are you even still surprised that the fibonacci sequence is popping up here? Anyways, this seems to suggest that . However, in order to prove this, we first need to unravel the behavior of . Using a similar method as above, we generate the following values for

Hmm, it looks like . This suggests that . We show this inductively on consecutive naturals .

#### Show that

We start off with the proposition . As we’ve observed previously that , we now outline the inductive step.

Show that

This concludes our proof that .

#### Show that

We also prove the proposition inductive on the naturals. Informally, we make the substitution of into the definition of in order to get closed in terms of .

(1)

As we’ve observed previously that , we now outline the inductive step.

Show that

It’s alright, it’s okay to yell out what the fuck. Anyways, this concludes our proof that .

Therefore, it follows naturally that from the above.

Woosh