# The Fib-Fib-Fib Sequence

Consider the sequences , defined recursively by

Show that

- 8 August, 2012 -
- Article, Math Problems -
- Tags : algebra, analysis, titu
- 0 Comments

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.