isiaiah d
Badges: 18
Rep:
?
#1
Report Thread starter 4 weeks ago
#1
Hey im having a little trouble with this:

S(nCm) = 2^n

So far ive wrote first few terms and have got that it will be 2+ something but can't figure out what the rest comes out to
0
reply
RDKGames
Badges: 20
Rep:
?
#2
Report 4 weeks ago
#2
(Original post by isiaiah d)
Hey im having a little trouble with this:

S(nCm) = 2^n

So far ive wrote first few terms and have got that it will be 2+ something but can't figure out what the rest comes out to
You can prove this by induction.

Or do u need to actually need to deduce the 2^n result?
0
reply
isiaiah d
Badges: 18
Rep:
?
#3
Report Thread starter 4 weeks ago
#3
(Original post by RDKGames)
You can prove this by induction.

Or do u need to actually need to deduce the 2^n result?
it says show that ""="" so im not sure - its from a uni prep problem sheet and im not sure proof by induction would be assumed knowledge?
0
reply
RDKGames
Badges: 20
Rep:
?
#4
Report 4 weeks ago
#4
(Original post by isiaiah d)
it says show that ""="" so im not sure - its from a uni prep problem sheet and im not sure proof by induction would be assumed knowledge?
I'd think so since its an A Level topic.

Even if you want to do this from scratch, you can test the sum for the first few values of n, notice powers of 2, conjecture that the sum is a power of 2 depending on n, then prove the result via induction. You would still show the result.
0
reply
isiaiah d
Badges: 18
Rep:
?
#5
Report Thread starter 4 weeks ago
#5
(Original post by RDKGames)
I'd think so since its an A Level topic.

Even if you want to do this from scratch, you can test the sum for the first few values of n, notice powers of 2, conjecture that the sum is a power of 2 depending on n, then prove the result via induction. You would still show the result.
Thanks, do you think you could give me a hand with the next one too please?:

show that (N-1)C(r) + (N-1)C(r-1) = nCr, can I also just prove that by induction? I tried manipulating it but went wrong somewhere and got
LHS = (N+1)^2 * nCr
0
reply
ghostwalker
  • Study Helper
Badges: 16
#6
Report 4 weeks ago
#6
(Original post by isiaiah d)
Thanks, do you think you could give me a hand with the next one too please?:

show that (N-1)C(r) + (N-1)C(r-1) = nCr, can I also just prove that by induction? I tried manipulating it but went wrong somewhere and got
LHS = (N+1)^2 * nCr
I wouldn't use induction on that one.

If you rewrite everything on the left in factorial format to start, then get everything over a common denominator (look to the RHS to see what denominator you're aiming for), it drops out in a couple of lines.

Post your working if it's still not coming out.
1
reply
isiaiah d
Badges: 18
Rep:
?
#7
Report Thread starter 4 weeks ago
#7
(Original post by ghostwalker)
I wouldn't use induction on that one.

If you rewrite everything on the left in factorial format to start, then get everything over a common denominator (look to the RHS to see what denominator you're aiming for), it drops out in a couple of lines.

Post your working if it's still not coming out.
yh sorry, just got it out right, was struggling a bit with my factorial definitions
1
reply
DFranklin
Badges: 18
Rep:
?
#8
Report 4 weeks ago
#8
(Original post by isiaiah d)
it says show that ""="" so im not sure - its from a uni prep problem sheet and im not sure proof by induction would be assumed knowledge?
A very short proof of this follows from considering the binomial expansion of (1+1)^n
0
reply
I hate maths!
Badges: 10
Rep:
?
#9
Report 4 weeks ago
#9
(Original post by DFranklin)
A very short proof of this follows from considering the binomial expansion of (1+1)^n
Also, obligatory counting argument:

The right-hand side tells you now many subsets there are of an n-element set, because each element has two states: it's either in the subset or not, hence 2*2*...*2 = 2^n. The left hand side tells you exactly the same thing, nCk tells you how many k-element subsets there are, and summing over k gets you all subsets.
0
reply
I hate maths!
Badges: 10
Rep:
?
#10
Report 4 weeks ago
#10
(Original post by isiaiah d)
show that (N-1)C(r) + (N-1)C(r-1) = nCr, can I also just prove that by induction? I tried manipulating it but went wrong somewhere and got
LHS = (N+1)^2 * nCr
Oh I just saw this question too, I'll add a counting argument here as well (where possible I really enjoy counting). I also just realised you probably just started uni so I'll avoid using set terminology.

Let's say we have a collection of letters, for example {a,b,c,d,e,f} (in this case n=6). Let's say I want to choose three letters: 6C3=20 represents how many ways I can choose 3 letters from this collection, e.g. {a,b,c}, {a,b,d}, {a,b,e}.

Now let's say I break up this collection into two separate ones: {a,b,c,d,e} and {f}. If I still want to get three letters from these collections, then I can either pick all three letters from the first collection (5C3) or I can pick two letters from the first collection and also pick the "f" from the second collection (5C2 * 1C1 = 5C2). But this is the same as if I just wanted to choose just three letters from my original collection of {a,b,c,d,e,f}. Hence 5C3+5C2=6C3.

You can make a more general argument with a collection of n things and choosing r things (i.e. an n-element set and forming an r-element subset).
1
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • The University of Law
    The Bar Series: Applications and Interviews - London Bloomsbury campus Postgraduate
    Thu, 17 Oct '19
  • Cardiff Metropolitan University
    Undergraduate Open Day - Llandaff Campus Undergraduate
    Sat, 19 Oct '19
  • Coventry University
    Undergraduate Open Day Undergraduate
    Sat, 19 Oct '19

How has the start of this academic year been for you?

Loving it - gonna be a great year (142)
17.95%
It's just nice to be back! (213)
26.93%
Not great so far... (283)
35.78%
I want to drop out! (153)
19.34%

Watched Threads

View All