4

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.

HeroZhang001
  • 2,201
tantan69
  • 145
  • "I figured out that a subset of size 1 has 2 elements" : I don't understand this. There are $26$ distinct subsets possible from the original set of elements ${a,b,\cdots,z}$ such that the subset has only 1 element. Namely, the $26$ subsets ${a}, {b}, \cdots, {z}.$ What am I missing here? – user2661923 Feb 19 '23 at 03:50
  • @user2661923 a subset contain {a} has 2 subsets. A set containing {a,b} has 3 elements, a set containing {a,b,c} contains 5 elements, etc. – tantan69 Feb 19 '23 at 03:54
  • Oh, I see what you are saying. You mean that there are $2^1$ possible subsets that can be formed if the elements in these subsets are limited to the elements in ${a}$, and $[2^2] - 1$ possible subsets that can be formed if these subsets are limited to the elements in ${a,b}$, because one of these subsets, namely ${a,b}$ itself is forbidden, since it violates the constraint of having a set with two consecutive letters. – user2661923 Feb 19 '23 at 04:02

2 Answers2

4

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$.

Caleb Stanford
  • 45,895
0

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)."

PSWadder
  • 66