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
1111 bronze badge
$endgroup$
2
add a comment |

1 answer 1


active earliest Votes
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
16588 bronze badges
$endgroup$
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
submit

Post together a guest


name
email Required, but never shown


Post together a guest


name
email

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
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
subscribe to RSS
concern feed To subscribe to this RSS feed, copy and also paste this URL right into your RSS reader.


*

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.