Find a linear reccurrence relation where a(n) is the number of subsets of {1,2,3,...,n} not containing three consecutive numbers.

Question

Find a linear constant coefficient for the recurrence relation $a(n)$ where $a(n)$ is the number of subsets of $\{1,2,3,\dots,n\}$ not containing three consecutive numbers.

So $a(n)$ must have a recurrence relation where it can be traced that the the two numbers are not greater or higher than the first?

This is a duplicate of http://math.stackexchange.com/questions/86249/number-of-subsets-of-1-2-ldots-n-containing-no-three-consecutive-intege?rq=1 , although that question wasn't answered so I recommend leaving this one open. — Michael Lugo, May 11 '15 at 13:14

score 2 · Answer 1 · answered May 11 '15 at 12:52

2

Let $A(n)$ be the number that don't include $n$.
Let $B(n)$ be the number that include $n$ but not $n-1$.
Let $C(n)$ be the number that include $n$ and $n-1$.
Find recursions for all three.

answered May 11 '15 at 12:52

Empy2

50,853

1

I think that's the hard way, but since Tom's assignment isn't due yet, I'll wait a while. – Gerry Myerson May 12 '15 at 13:22

Find a linear reccurrence relation where a(n) is the number of subsets of {1,2,3,...,n} not containing three consecutive numbers.

1 Answers1