# How many subsets of {1, 2, 3, … 10} do not contain any pair of consecutive integers? [duplicate]

How would I solve this problem? Thanks in advance.

## marked as duplicate by Math1000, lulu, Ross Millikan combinatorics StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); May 26 at 0:35
• There are few enough you can just list and count them. It will take a little while, but you might see the pattern. If you put in $1$ you can't put in $2$ and so on. – Ross Millikan May 26 at 0:37
Such a subset of $$\{1,2,\ldots,n\}$$ either does not contain $$n$$ and hence is such a subset of $$\{1,2,\ldots,n-1\}$$, or it contains $$10$$ and the rest is such a subset of $$\{1,2,\ldots, n-2\}$$. Use his to find a recursion formula and recognize this. as famous