Q: How countless subsets does the set \$1,2,3,...n\$ have actually that save on computer no 3 consecutive integers? uncover a recurrence.

You are watching: How many subsets does the set {1, 2, 3} have?

I nothing think I recognize the solution.

According to the systems if i take out \$n-1\$ native \$1,2,3,ldots , n-1, n\$, then ns would have \$S_n-2\$ come the left that \$n-1\$, which i get, yet then I have ‘\$n\$’ which i don’t know what to do with. Because that every subset connected with \$S_n-2\$, there’s currently an element ‘\$n\$’ easily accessible to either incorporate or not include in the subset, which boosts the size of \$S_n-2\$. If pretend ‘\$n\$’ isn’t there it would give us \$S_n-2\$ exactly.

The very same goes for \$S_n-2\$ and also \$S_n-3\$. The \$S_n\$ would certainly then it is in a reduced bound.

What am I no getting around this question?

combinatorics recurrence-relations
share
point out
monitor
edited Dec 13 "19 at 6:28
user694818
inquiry Dec 12 "19 at 23:58

noname123noname123
\$endgroup\$
2

3
\$egingroup\$
Let \$A subseteq 1, 2, cdots, n \$ satisfies the condition.We deserve to divide to 3 cases:

\$n ot in A\$: Then, there room \$S_n-1\$ possibilities because that \$A\$\$n in A\$:\$n-1 ot in A\$ : Then, there room \$S_n-2\$ possibilities that \$A\$ because \$A - \$ is three-consecutive-integer-free and also belongs come \$1, 2, cdots, n-2\$.\$n-1 in A\$: Then, \$n-2 ot in A\$. Currently we have actually \$A - -1, n subset 1, 2, cdots, n-3\$, therefore there room \$S_n-3\$ possibilities because that \$A\$.

Therefore, \$S_n = S_n-1 + S_n-2 + S_n-3\$.

re-superstructure
mention
monitor
answer Dec 13 "19 in ~ 4:33

leejseoleejseo
\$endgroup\$
include a comment |

Thanks for contributing response to sdrta.net Stack Exchange!

But avoid

Asking for help, clarification, or responding to various other answers.Making statements based on opinion; back them increase with references or an individual experience.

Use sdrta.netJax to layout equations. sdrta.netJax reference.

To find out more, see our tips on writing good answers.

See more: Calories In 1/2 Pound Ground Beef, Ground Beef Nutrition Facts

Draft saved

authorize up making use of Facebook
authorize up utilizing Email and also Password
submit

### Post together a guest

name
email Required, but never shown

### Post together a guest

name
email

Required, yet never shown

## Not the prize you're feather for? Browse various other questions tagged combinatorics recurrence-relations or ask your own question.

Featured top top Meta
connected
1
number of subsets of \$1,2, ldots, n\$ comprise no three consecutive integers: recurrence equation?
2
Recurrence relation for number of subsets the contain no continually integers
2
\$4\$-element subsets the the collection \$1,2,3,ldots,10\$ that execute not contain any type of pair of consecutive numbers
3
setup up a recurrence relationship of ternary strings of size n the does not have three consecutive 1s
2
How plenty of subsets room there the contain a specific set?
1
How numerous subsets the \$A=,1,2,...,n\$ are there such that no consecutive number come with each other
2
How numerous subsets contain no 3 continually elements?
0
Recurrence relation because that the number of bit strings of size n that do not contain three consecutive 0s versus 3 consecutive 1s.
5
A same dice is to be rolled \$n\$ times. Discover the probability that not gaining three consecutive sixes.
warm Network inquiries an ext hot questions

concern feed

sdrta.net
agency
ridge Exchange Network
site style / logo © 2021 ridge Exchange Inc; user contributions license is granted under cc by-sa. Rev2021.11.5.40661

sdrta.netematics ridge Exchange works finest with JavaScript permitted

her privacy

By click “Accept all cookies”, girlfriend agree stack Exchange can store cookie on your maker and disclose details in accordance v our Cookie Policy.