# Super Fibonacci

Show that where defined as

- 7 August, 2012 -
- Article, Math Problems -
- Tags : number theory, titu
- 0 Comments

### 1. Guess at a solution

Let’s start off by enumerating these terms

Since the problem asks us to prove that , let’s just see what we get left over after dividing out

Oh my god! That’s the fibonacci sequence defined by

This naturally suggests that

### 2. Show that

We can prove this inductive on consecutive naturals . Informally, We form the inductive steps through the regrouping of the terms of as

#### Proof by induction

We need to prove the proposition holds for all .

As the base cases, we observe that and hence .

Show that

This concludes our proof that .

### 3. Show that

Since is successively defined in terms of addition on the naturals, which closes the naturals, then it must be the case that for any , . Because , then trivially . This concludes the proof that .