If we have a set that is the alphabet, $\{a,b,..y, z\}$ then how many subsets exist that do not contain consecutive letters?
I figured out that a subset of size $1$ has $2$ elements, size $2$ has $3$ elements, size $3$ has $5$ and so on which is the fibonacci sequence.
So far I am trying to prove $S{(n+1)}= S{n}+S({n-1})$ but I am stuck. I am trying to prove it then prove by induction that $S(n)= F({n+2})$ where $F(n)$ is the fibonacci sequence.
On
You have the base cases so I'll just discuss the indictive step:
We assume for up to and including n and want to prove this recurrence for an alphabet with n+1 letters.
Take an element in S(n+1). If the (n+1)th letter is in your element, then the nth letter cannot be. Therefore, removing the (n+1)th letter creates an element of S(n-1). You in fact recover every element of S(n-1) by removing (n+1) from every subset of S(n+1) containing the letter (n+1).
Alternatively, if you do not have the (n+1)th letter, then that is an element of S(n) and is in fact all of S(n).
Thus you get the desired recurrence, S(n+1)=S(n)+S(n-1).
Since you already have the base cases, all that remains is to say "Notice this follows the same recurrence as the Fibonacci sequence and S(1)=F(3), S(2)=F(4), thus S(n)=F(n+2)."
Everything you did so far is good! To prove the recurrence, let's consider the example $S(26)$. Consider whether or not the subset has the letter $z$ in it.
If it does have $z$, then it can't have $y$. So the remainder can be any subset of $\{a, b, c, \ldots, x \}$, of which there are $S(24)$ possibilities.
If it does not have $z$, then it can be any subset of $\{a, b, c, \ldots, y\}$, of which there are $S(25)$ possibilities.
Therefore, we have $S(26) = S(25) + S(24)$. The same argument generalizes from $26$ to any $n \ge 2$.