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
point out
edited Dec 13 "19 at 6:28
inquiry Dec 12 "19 at 23:58

1111 bronze badge
add a comment |

1 answer 1

active earliest Votes
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$.

answer Dec 13 "19 in ~ 4:33

16588 bronze badges
include a comment |

your Answer

Thanks for contributing response to sdrta.net Stack Exchange!

Please be sure to answer the question. Administer details and share your research!

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
Draft discarded

Sign up or log in

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

Post together a guest

email Required, but never shown

Post together a guest


Required, yet never shown

write-up Your price Discard

By clicking “Post your Answer”, friend agree come our regards to service, privacy policy and also cookie policy

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

Featured top top Meta
number of subsets of $1,2, ldots, n$ comprise no three consecutive integers: recurrence equation?
Recurrence relation for number of subsets the contain no continually integers
$4$-element subsets the the collection $1,2,3,ldots,10$ that execute not contain any type of pair of consecutive numbers
setup up a recurrence relationship of ternary strings of size n the does not have three consecutive 1s
How plenty of subsets room there the contain a specific set?
How numerous subsets the $A=,1,2,...,n$ are there such that no consecutive number come with each other
How numerous subsets contain no 3 continually elements?
Recurrence relation because that the number of bit strings of size n that do not contain three consecutive 0s versus 3 consecutive 1s.
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
subscribe to RSS
concern feed To subscribe to this RSS feed, copy and also paste this URL right into your RSS reader.


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.