# summation helpWatch

Announcements
#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
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
#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
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
#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
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
#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
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
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
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
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

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

### University open days

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

### Poll

Join the discussion

#### 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%