Can anybody prove the conjecture that

for all natural n and all real x?

For all complex x?

ⁿC_i denotes 'n choose i'

Tom.

Let's denote n choose r as C(n,r).

We know:

(1 + y)n =

n å i=0

C(n,i)yi

Differentiate:

n(1 + y)n-1 =

n å i=0

C(n,i)i yi-1

So:

n y(1 + y)n-1 =

n å i=0

C(n,i)i yi

Substitute y = x/(1 - x) so 1 + y = 1/(1 - x):

n[x/(1 - x)] * 1/(1 - x)n-1 =

n å i=0

C(n,i)i xi /(1 - x)i

Then multiply through by (1 - x)ⁿ and the answer comes out.

Nice. Thanks.

What does n choose r mean?

The usual notation for n choose r is ⁿ C_r . It represents the number of ways of 'choosing' r objects from a set of n objects (in any order), i.e. ³ C₂ = 3, as there are 3 ways of choosing 2 objects from a set of 3 (providing they are all unique). The formula is:

ⁿ C_r = n!/[r!(n-r)!].

Olof

Brad, it's a very useful combinatorial function. It means the number of ways of choosing r objects from n (where the objects are distinct). For instance, 3 choose 2 is 3 because the number of ways of choosing 2 elements from {1,2,3} is 3, they are {1,2},{2,3} and {1,3}. In fact, there is a formula for it: n choose r = ⁿ C_r = n!/(r!(n-r)!).

What a strange coincidence, almost word for word the same.

Wow that is quite scary J

Hi Michael,

Can i just ask you how you managed to think of such a method. These kind of questions just really annoy me because the solutions seem so straight forward, it's just being able to think in such a lateral way to be able to find them!

Eg. How did you know to make the substitution and how did you know which subs. to make?

Thank-you in advance

There really is no lateral thinking involved. If you look at the right hand side of Tom's identity, it is clear that if you ignore the C(n,i) and the i then the consecutive terms have a common ratio. It is natural to take out a factor of (1 + x)ⁿ and so you're left needing to prove something like:

nx/(1 - x)n =

n å i=1

i C(n,i) xi (1 - x)-i

This can be re-arranged as:

nx/(1 - x)n =

n å i=1

i C(n,i) (x/(1-x))i

Or:

nx/(1 - x)n =

n å i=0

i C(n,i) (x/(1-x))i

(when i = 0 the relevant term is 0).

What could be more natural now than to try a substitution like y = x/(1 - x)? Once you do that you simply need to remember the binomial expansion, and then differentiate term by term, and the answer comes out quickly.

PS. Technically you need to check the case x = 1 separately, but this is easy.

Here's another way of looking at the problem. Let X₁ ,X₂ ,...,X_n be independent random variables, taking value 1 with probability x and 0 with probability 1-x. Now compute the expectation of:

X₁ + X₂ + ... + X_n

in two different ways, equate the result and we get Tom's identity. Of course this assumes that p is in [0,1] but since each side of the identity is a polynomial, it follows that the polynomials must be identically the same so Tom's identity holds for all complex x.

Prove that given any n unit vectors v₁, ... ,v_n there are numbers e₁, ..., e_n such that e_i = ±1 and

|

n å i=0

ei vi| £ Ön

.

If possible, try and prove it using a probabilistic argument like Michael used above. If nobody gets it I'll post the answer in a couple of days. Your proof should only be about 3 or 4 lines at most. As a hint, you might want to consider the expected value E[e_i e_j ] for any pair i, j and see if this gives you any ideas where to go from there.

Note: thanks to my combinatorics supervisor Jacques Verstraete for showing me this excellent little proof.

Let the e_i be independent random variables taking the values 1 or -1 with probability 1/2. Let

X=

n å i=1

ei vi

.

E[X2]=E[

å i,j

eiejvi. vj ]=

å i,j

E[eiej]vi .vj

. But E[e_ie_j]=1 if i=j (since e_i² = 1), or (using the fact that e_i and e_j are independent) if i ¹ j then E[e_ie_j]=E[e_i]E[e_j]=0. So

E[X2]=

n å i=1

vi2 = n

. If |X| > Ön for all choices of e_i then E[X²] > n, hence there is at least one choice of e_i such that |X| £ Ön.