## How would I prove this? (some trick with factorials?)

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

4=5
Posts: 2073
Joined: Sat Apr 28, 2007 3:02 am UTC

### How would I prove this? (some trick with factorials?)

I was playing around and empirically identified this relation
x and n are non-negative integers.

[; \frac{1}{(n+x+1)} = \sum_{i=0}^{n} \frac{(-1)^{i}(n+x)!}{x!i!(n-i)!(x+i+1)} ;]

How would I go about proving it?

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: How would I prove this? (some trick with factorials?)

Induction on n.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Parralelex
Posts: 74
Joined: Sun Dec 02, 2012 8:10 am UTC
Location: Location Location

### Re: How would I prove this? (some trick with factorials?)

I put the "fun" in "mathematics".

And then I took it back out.

gmalivuk
GNU Terry Pratchett
Posts: 26830
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: How would I prove this? (some trick with factorials?)

Incidentally, the [math] tags haven't been functional on here for quite some time. However, if you use the TeX The World plugin, putting ;] at the end of what you want TeXified and [; at the beginning will do the trick.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

### Re: How would I prove this? (some trick with factorials?)

I generally try to rewrite conglomerations of factorials as choose functions in hopes of making a counting argument, so I tried to coalesce the sea of factorials on the right-hand side into choose functions. I got it as a product of these, but I never got a counting argument working, and instead I had to rely on some... intriguing choices of substitutions and identities to get the answer. A proof of the identity follows.

Spoiler:
First, the non-integral fraction on the left-hand side will be an annoying target, so I would suggest multiplying through by (n+x+1). The factor of (n+x+1) on the right-hand side can be nestled into the numerator's factorial, producing 1 = \sum_{i=0}^{n} \frac{(-1)^{i}(n+x+1)!}{x!i!(n-i)!(x+i+1)}. From here on, we work on evaluating the right side.

The x!i!, alongside the (x+i+1), suggests (x+i choose x). (x+i choose x) = (x+i)!/(x!i!), so x!i! = (x+i)!/(x+i choose x), and hence the sum equals sum_{i=0}^n { (-1)^i (n+x+1)! (x+i choose x)}/{ (x+i+1)! (n-i)!}. The remaining three factorials make a choose function as well, so we get sum_{i=0}^n (-1)^i (n+x+1 choose x+i+1) (x+i choose x).

Here's where things get a little wonky. The fact that the bottom of one choose function is so close to the top of the other without being equal is irksome, so I push to make them the same. I tried factoring out a quotient from one of the choose functions (i.e. (n+x+1 choose x+i+1) = (n+x choose x+i) (n+x+1)/(x+i+1)), but the factor of x+i+1 in the denominator never went away and messed up the sum no matter what I tried. I then tried the next method I had of reducing the lower number in a choose function by one: the identity (a+1 choose b+1) = sum_{j=0}^a (j choose b). Applying that, we get sum_{i=0}^n (-1)^i sum_{j=0}^{n+x} (j choose x+i) (x+i choose x).

Now the bottom number in one choose function matches the top number in the other, so we can apply this identity: (a choose b) (b choose c) = (a choose c) (a-c choose b-c). This gives us sum_{i=0}^n (-1)^i sum_{j=0}^{n+x} (j choose x) (j-x choose i). The benefit here is that we have restricted the i to a single choose function, where before it was in both.

To capitalize on this, we swap the order of summation. Moving the sum_j to the outside gives us sum_{j=0}^{n+x} sum_{i=0}^n (-1)^i (j choose x) (j-x choose i), and then we factor the (j choose x) out of the inner sum, yielding sum_{j=0}^{n+x} (j choose x) sum_{i=0}^n (-1)^i (j-x choose i).

This inner sum, sum_{i=0}^n (-1)^i (j-x choose i), is an identity as well. sum_{i=0}^n (-1)^i (a choose i) = (-1)^n (a-1 choose n), unless a = 0, in which case the sum is 1. (I had to derive this myself; it can be derived using (a choose b) = (a-1 choose b-1) + (a-1 choose b), which holds when a >= 1, and observing that the sum telescopes.) So sum_{i=0}^n (-1)^i (j-x choose i) = (-1)^n (j-x-1 choose n), except when j = x. Substituting this into our expression, we get [sum_{j=0 to n+x, j =/= x} (j choose x) (-1)^n (j-x-1 choose n) ] + (x choose x) * 1 , where the last term is the j = x term.

Now, as long as 0 <= j <= n+x, j-x-1 is strictly less than n, so (j-x-1 choose n) = 0. Then, [sum_{j=0 to n+x, j =/= x} (j choose x) (-1)^n (j-x-1 choose n) ] + (x choose x) * 1 simplifies to [sum_{j=0 to n+x, j =/= x} (j choose x) (-1)^n 0 ] + 1 * 1 = 0 + 1 = 1, as desired.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.