Fruits of procrastination

Month: March, 2019

A cute combinatorial identity

Just wanted to record a cute combinatorial argument. Prove that      \sum\limits_{i=0}^n {n\choose i} {i\choose m}= {n\choose m} 2^{n-m}

I read this formula in the article “Pascal functions” in “The American Mathematical Monthly”.

They prove it using the new machinery of Pascal functions that they develop in the article. I tried proving it using an algebraic argument, but couldn’t find the right formulation. I could finally prove it using a combinatorial argument, which I have explained below:

The left hand side counts the number of ways of first selecting i items from n items, and then selecting m items from those already-selected i items. Obviously, for i<m, this does not make sense. Hence, {i\choose m}=0 in those cases. For i\geq m, the above interpretation is valid.

We can interpret the right hand side as the number of ways of selecting m items from n items, and then going to each of the left-over items (there are n-m of them) and deciding if they had been pre-selected or not. Here pre-selection implies being selected amongst the i items, out of which the final m items have been chose.

Hence, the right hand side equals the left hand side.

Some solutions

I solved two math problems today. The solutions to both were uniquely disappointing.

The first problem was the first problem from IMO 1986:

Let d be a number that is not 2,5 or 13. Prove that out of the set \{2,5,13,d\}, we can select two different numbers a,b such that ab-1 is not a square.

A quick check would show that 2.5-1, 2.13-2 and 5.13-1 are all squares. This shows that of the two numbers that we select from \{2,5,13,d\}, one of them has to be d. We essentially need to prove that for d\neq 2,5,13, 2d-1, 5d-1 and 13d-1 are not all squares (a maximum of two of them might be. But all three cannot).

I tried figuring out some of the implications of all of them being squares, but couldn’t come up with anything concrete, as I didn’t write anything at all, and just tried to devise a strategy mentally. Ultimately, I came up with possibly the most mundane proof of all time.

Proof: Consider squares \mod 16 (I couldn’t come up with any contradiction up until \mod 8). The possible residues for squares \mod 16 are 0,1,4,9. Now my strategy was to plug in all possible residues \mod 16 in place of d, and checking that in every such instance, at least one of 2d-1, 5d-1 and 16d-1 gave a residue that was not 0,1,4,9\mod 16. This I could successfully verify. Hence proved.

The solution that I could find in the IMO compendium was much smarter, but involved some algebra that would obviously involve putting pen to paper.

The second question that I solved today was proving the Koszul formula, which states that

2g(\nabla_X Y,Z)=D_Xg(Y,Z)+D_Yg(X,Z)-D_Zg(X,Y)-g([Y,X],Z)-g([X,Z],Y)+g([Z,Y],X)

I’d seen proofs before in textbooks, that would involve writing down expansions, and then combining all of them in some clever way. The way that I came up with was pretty algorithmic, and perhaps even more elementary. It is simply the following: Take g(\nabla_X Y,Z). Use the torsion free condition to write it as g(\nabla_Y X,Z)+g([X,Y],Z). Now use the formula for connection acting on a tensor to write g(\nabla_Y X,Z) as D_Y g(X,Z)-g(X,\nabla_Y Z). Performing the two operations, we have D_Yg(X,Z)-g(X,\nabla_Y Z)+g([X,Y],Z). Performing this operation of first using the torsion free condition and then the formula for a connection on a tensor three times, we get the Koszul formula.

Effective Altruism – March

I’m recording the payment I made to Effective Altruism in the month of March, to keep my pledge of donating 10% of my lifetime income to it.

Screen Shot 2019-03-08 at 10.24.55 AM

I had said that I’ll soon write an article about causes that concern me/that I want to make monetary contributions to. Some articles that I read in the recent past are the wiki article on poverty in India, sexual injustice in rural India, and also Tolstoy’s views on charity and religion (which for sure have changed the world. For starters, Gandhi pretty much took all of his views and practices from Tolstoy, almost verbatim, which of course decided the course for Indian self-determination). However, I feel that I have not read enough to write anything original/meaningful. Hopefully this will change by next month.

Here’s a slightly badly written proof to a competitive math problem. I guess I could expand it slightly if readers find it unreadable.

The following is a question from the International Mathematics Competition, 1994.

Prove that in any set S of 2n-1 different irrational numbers, there exist n irrational numbers \{s_1\dots,s_n\} such that for any \{a_1,\dots,a_n\}\in \Bbb{Q} such that

(1)  a_i\geq 0,\forall i\in\{1,\dots,n\} and (2)  \sum\limits_k a_k>0
\sum\limits_{i=1}^n a_is_i is also irrational.

Proof: We will prove this by induction. This is obviously true for n=1. Now let us assume that this is also true for n. We shall now prove the case for n+1: that amongst any 2(n+1)-1 different irrational numbers, there exist n+1 numbers such that the given condition is satisfied. We will prove this by contradiction. Let us call this 2(n+1)-1 element set A_{n+1}.
Remove any two elements from A_{n+1}. We get 2n-1 elements. By the inductive hypothesis, there exist n elements \{s_1,\dots,s_n\} such that for any \{a_1,\dots,a_n\} non-negative rational numbers amongst which at least one is strictly positive, \sum\limits_{i=1}^n a_is_i is irrational. Let us call this set of elements S_n. Now one by one, add each element of A_{n+1}\setminus S_n, to S_n to form n+1 element sets. If each of these n+1 element sets can be put into some linear combination to give us a rational number, then we can subtract the right rational linear combination of A_{n+1}\setminus S_n (which by our assumption should also be rational) to give us S_n back, which should again be a rational number. But that is a contradiction. Hence, there has to exist an n+1 tuple of elements in A_{n+1} too such that no linear combination with non-negative rational coefficients, such that at least one coefficient is positive, can give us a rational number.