# 7 - Recursion (1), Fibonacci numbers, xx-free (bit)strings

## Recursive functions
A function that calls itself until some base case.

The definition of the function involves the function itself.

**Ex:**

**Claim:**
$f(n) = 3\times 2^{n+1}-3$

**Proof by induction on the value of $n$:**
Base case:
$n=0, f(0)=3$
$f(0)=3\times2^{0 + 1}-3 = 6-3=3$

Inductive step:
Assume $f(k)=3\times2^{k+1}-3$
for all $k \in \{0,1,2,...,n-1\}$ (inductive hypothesis)

Proove for $f(n)$
$f(n) = 2\times f(n-1)+3$ (Definition of $f(n)$)
$f(n) = 2 \times (3 \times 2^{n}-3) + 3$ (Replace $f(n-1)$ with formula) (inductive hypothesis)
$f(n) = 3 \times 2^{n+1}-6 + 3$
$f(n) = 3\times 2^{n+1} -3$
Q.E.D $\blacksquare$

---
 factorial

---
 Pascal's identity
$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

---
## Fibonacci function

**Claim:**
$f(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}$ where

$\phi = \frac{1 +\sqrt{5}}{2}$, $\psi = \frac{1-\sqrt{5}}{2}$

$\phi$ and $\psi$ are the solutions to $x^2 = x+1$

$\phi$ is the golden ratio
$\psi$ is... not

**Proof by induction on $n$:**
Base case: $n=0$

$f(0) = \frac{\phi^0 - \psi^0}{\sqrt{5}} = \frac{1-1}{\sqrt{5}}=0$

Base case: $n=1$

$f(1) = \frac{\phi^1 - \psi^1}{\sqrt{5}} = \frac{\frac{1 +\sqrt{5}}{2} - \frac{1-\sqrt{5}}{2}}{\sqrt{5}}=\frac{\sqrt{5}}{\sqrt{5}}=1$

Inductive step
Assume $f(k) = \frac{\phi^k - \psi^k}{\sqrt{5}}$
For all $k \in \{0,...,n-1\}$

$f(n) = f(n-1) + f(n-2)$ (Definition)
$f(n) = \frac{\phi^{n-1} - \psi^{n-1}}{\sqrt{5}} + \frac{\phi^{n-2} - \psi^{n-2}}{\sqrt{5}}$
$f(n) = \frac{\phi^{n-1} + \phi^{n-2} - (\psi^{n-1} + \psi^{n-2})}{\sqrt{5}}$
$f(n) = \frac{\phi^{n-2}(\phi + 1) - \psi^{n-2}(\psi + 1)}{\sqrt{5}}$
Note: $\phi + 1 = \phi^2$ because $phi = 1.618...$ and $\phi^2 = 2.618...$ Same for $\psi$
$f(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}$

$\phi \approx 1.618034$
$\psi \approx -0.618304$
$\psi^n \rightarrow 0$

This means that the fibonacci number as $n\rightarrow \inf$, $f(n) \rightarrow \frac{\phi^n}{\sqrt{5}}$

## Recursively defined sets
- 00-free bitstrings

Let $S_n$ be the set of $n$-bit binary strings that do no contain two consecutive 0's

Ex:

$S_0 = \{\epsilon\}$ (string of length 0) $|S_0| = 1$
$S_1 = \{1, 0\}$ $|S_1| = 2$
$S_2 = \{01, 10, 11\}$ $|S_2| = 3$
$S_3 = \{010,101,110,111,011\}$ $|S_3| = 5$

How big is $S_n$?

A string in $S_n$ either
- Starts with a 1, followed by any string in $S_{n-1}$ XOR
- Starts with a 01 followed by any string $S_{n-2}$

- There are $n-1$ positions after the first one. As long as there are no consecutives 0's in those positions, then the whole string will not have two consecutives 0's. Same for the 01 case
- We partition the strings that start with 1 and the strings that start with 01 into two sets $A$ and $B$.
- Then $S_n = A \cup B$ where $A$ and $B$ are disjoint
- By the sum rule, $|S_n| = |A| + |B|$
- $|S_n| = |S_{n-1}| + |S_{n-2}|$


This sequence is very similar to the fibonacci sequences, just offset. This sequence starts at the second 1 in the fibonacci sequence

$|S_n| = fibonacci(n+2)$

## aa-free strings over $\{a,b,c\}$

We try to look at the previous recurrence relation to see if we can find any similarities.

A string in $S_n$ either
- Starts with a b followed by any string in $S_{n-1}$ OR
- Starts with a c followed by any string in $S_{n-1}$
- Starts with ab followed by any string in $S_{n-2}$
- Starts with ac followed by any string in $S_{n-2}$


**Claim:**

$|S_n| = \frac{(3-2\sqrt{3})(1-\sqrt{3})^n +(3+2\sqrt{3})(1+\sqrt{3})^n}{6}$
$\alpha = (1-\sqrt{3})^n$ $\beta = (1+\sqrt{3})^n$
$\alpha$ and $\beta$ solve $x^2=2x+2$

## ab-free strings over $\{a,b,c\}$
Let $S_n$ be the set of $n$-bit binary strings that do not contain ab as a consecutive substring


A string in $S_n$ either
- Starts with b followed by any string in $S_{n-1}$ OR
- Starts with c followed by any string in $S_{n-1}$
- Starts with ac followed by any string in $S_{n-2}$
- Starts with aac followed by any string in $S_{n-3}$

This patern of starting with a series of a's until a c repeats. We get a recurence pattern

$|S_n| = 2\times |S_{n-1}| + \sum_{k=0}^{n-2}|S_k|$
###### tags: `COMP2804` `Recursion`