Maths help?

[Jerrek]

Hey guys... I'm looking for some answers here.

Given:

http://home.cogeco.ca/~johannj/net_stuff/combin.jpg

I need to give a combinatorial proof of this identity, and I also need to give an algebraic proof for this identity.

Now the combinatorial part is relatively easy if I understand it. Basically, on the left you're counting the number of even sets (2i being even) and on the right you're counting the number of odd sets (2i + 1 being odd). So, given a set S it gets mapped to:

[ {1, 2, ..., n} \ S, if n is not an element of S
[ ({1, 2, ..., n} \ S) UNION {n}) if n is an element of S

So basically you have a one to one correspondence:

For example, given a set {1, 2, 3}, you have:

{1}, {2}, {3}, {1, 2, 3} -- odd subsets

{2,3}, {1,3}, {1,2}, empty set -- even subsets

See? Each one of the odd subsets has a complement in the even subsets.


Now the question is... how to prove this algebraiclly? They give a hint to expand (1 - 1)^n. Eh. Help?

[Jerrek]

You guys are losers. :p

[Bill Payer]

Originally posted by Jerrek
You guys are losers. :p

I trust you're not expecting any help, after that!

[zoombini]

Is by chance, the answer 42 ??

[Theodoric]

Originally posted by Jerrek
You guys are losers. :p
On the other hand, 1 - 1, as quoted by you, is 0 and 0^n is 0. Now, if you actually meant to write (1-i)^n, then I'd hazard a wildish guess that what is being suggested is a binomial expansion, the coefficients of which, if my rusty memory serves me right, are connected to various combinatorial terms. :)

[Jerrek]

Combinatorics suck. Look at this assignment that I have to complete by tomorrow noon:

http://www.student.math.uwaterloo.ca/~math239/fall2003/asst2.pdf

[Theodoric]

Originally posted by Jerrek
Combinatorics suck. Look at this assignment that I have to complete by tomorrow noon:

http://www.student.math.uwaterloo.ca/~math239/fall2003/asst2.pdf

Well, problem 1(a) is easy, obviously intended to build up your confidence. :)

(1 - x^2)/(1 + x^3)

Factorise top and bottom

(1 - x)(1 + x)/(1 + x)(1 - x +x^2)

Cancel out the (1 + x)

(1 - x)/(1 - x + x^2)

Divide top & bottom by (1 - x)

1/(1 + x^2/(1 - x))

However, problems 1(b) onward confirmed my opinion that I was right to abandon maths after A-Level. :)

[Jerrek]

You need to do a combinatorics proof, not an algebraic one as you did... heh... This is a combinatorics course :p

[Theodoric]

Originally posted by Jerrek
You need to do a combinatorics proof, not an algebraic one as you did... heh... This is a combinatorics course :p
Er, a proof is a proof is a proof. The one I gave seemed perfectly valid to me, especially as the question paper was headed simply "Math 239 Assignment 2". I was always told to carefully read the rubrics before starting an exam paper, and I did so in this case.

So, pray enlighten us with the combinatorics proof.

[paulyoung666]

hang on you abuse people , question there answers and still want help , hang on who is doing this course you or people on this board :confused: , are you allowed help btw ;) :) :)

[MrSums]

If I read the equation correctly, the answer would appear to be $10m (as evidenced by this (http://www.guardian.co.uk/business/story/0,3604,1052435,00.html) link)