MathCastle
Proof WritingHardInduction

Induction · Hard problem

Let f(n)f(n) be the number of subsets of {1,2,…,n}\{1, 2, \ldots, n\} with no two consecutive numbers. Break down by whether nn is in the subset to get f(n)=f(n−1)+f(n−2)f(n) = f(n - 1) + f(n - 2), with f(1)=2f(1) = 2, f(2)=3f(2) = 3. What is f(10)f(10)?