# Prove that this system of linear equations generates $\left| \left( \begin{smallmatrix} 1/2 \\ n \end{smallmatrix} \right) \right|$ as a solution?

This infinite system of linear equations:

$$\begin{array}( 2x_1=1 \\ 3x_1+4x_2=2 \\ 4x_1+5x_2+6x_3=3 \\ \cdots \end{array}$$

In other words, this is particular case of a system:

$$\begin{array}( a_{11}x_1=b_1 \\ a_{21}x_1+a_{22}x_2=b_2 \\ a_{31}x_1+a_{32}x_2+a_{33}x_3=b_3 \\ \cdots \\ a_{m1}x_1+a_{m2}x_2+ \cdots + a_{mn}x_n + \cdots=b_m \\ \cdots \end{array}$$

With the coefficients given by:

$$a_{mn}=m + n~~~~~~~~~b_m=m$$

The systems seems to give the following sequence of solutions:

$$x_n= \left| \left( \begin{matrix} \frac{1}{2} \\ n \end{matrix} \right) \right|=\left(\frac{1}{2}, \frac{1}{8}, \frac{1}{16}, \frac{5}{128}, \cdots \right)$$

How can I prove that it's true?

Why does it happen? Can other fractional binomial coefficients be obtained this way (and how)? By 'this way' I mean a triangular system with simple regular sequence of integer coefficients.

I had some thoughts, and that's what I tried. Let's assume, that $x_n$ I found are really binomial coefficients. Then for $x_m$ we will have:

$$x_m= \left| \left( \begin{matrix} \frac{1}{2} \\ m \end{matrix} \right) \right|=\frac{1/2 (1-1/2)(2-1/2)\cdots (m-1-1/2)}{m!}=\frac{m-3/2}{m}x_{m-1}$$

$$x_m= \left(1- \frac{3}{2m} \right)x_{m-1}=x_1-\frac{3}{2}\left(\frac{x_1}{2}+\frac{x_2}{3}+\cdots+ \frac{x_{m-1}}{m} \right)$$

$$x_m=\frac{1}{2}-\frac{3}{2}\left(\frac{x_1}{2}+\frac{x_2}{3}+\cdots+ \frac{x_{m-1}}{m} \right)$$

On the other hand, from the $m^{th}$ equation we can derive:

$$x_m= \frac{b_m}{a_{mm}}-\frac{1}{a_{mm}}\left(a_{m1}x_1+a_{m2}x_2+\cdots+ a_{m,m-1}x_{m-1} \right)$$

$$x_m= \frac{1}{2}-\frac{1}{2m}\left((m+1)x_1+(m+2)x_2+\cdots+ (m+m-1)x_{m-1} \right)$$

I don't see how to get this relation into the same form as the previous one. Maybe I should modify it somehow.

• If you mean "in this way", yes. Every sequence can be produced as a solution to an infinite system of linear equations. – Christopher Carl Heckman Apr 18 '16 at 8:01
• @CarlHeckman, I also meant 'how'? – Yuriy S Apr 18 '16 at 8:02
• @CarlHeckman, also, could you please give me a reference for this statement? Where can I read about the connection between sequences and systems of linear equations? – Yuriy S Apr 18 '16 at 8:06
• You're going to get mad ... Just look at the system $x_1=a_1$, $x_2=a_2$, $x_3=a_3$, etc. Otherwise, you need to clarify what you mean by "this way". – Christopher Carl Heckman Apr 18 '16 at 8:07
• What are ${a_{mn}},\;{b_m}$? – user328032 Apr 18 '16 at 14:22

## 2 Answers

Since my hint in the comments was not followed up on, I'll elaborate in an answer.

Let $x_n = |\binom{\frac{1}{2}}{n}|$, and define:

$$A_m = (m+1)x_1+(m+2)x_2+\dots+ (m+m)x_m$$

What you are trying to show is that $A_m = m$ for all $m$. You already checked a few values that can be a base case for induction, so it will be enough to show that the sequences $A_1, A_2, \dots$ and $1,2,3...$ both satisfy the same recurrence.

The sequence $1,2,3,...$ satisfies an obvious recurrence, $b_m = 2b_{m-1}-b_{m-2}$, which encodes the fact that each term is the average of the term before it and the term after it. So now we just need to check the sequence $A_1, A_2, A_3, \dots$ also has this property. Luckily a lot of terms match up perfectly and we are just left with:

$$A_m+A_{m-2}-2A_{m-1} = 2mx_m + (3-2m)x_{m-1}$$

So in order for this recurrence relation to hold we just need to check that

$$2mx_m + (3-2m)x_{m-1} = 0$$

Which is easy to check by expanding $x_m = |\binom{\frac{1}{2}}{m}|$.

• Thank you. I did not follow your hint, because it wasn't clear to me how to do it. – Yuriy S Apr 23 '16 at 17:37

Alright, I figured it out. First, we write the recurrence relation for the absolute value of the binomial coefficients:

$$x_m= \left| \left( \begin{matrix} \frac{1}{2} \\ m \end{matrix} \right) \right|=\frac{1/2 (1-1/2)(2-1/2)\cdots (m-1-1/2)}{m!}=\frac{m-3/2}{m}x_{m-1}$$

$$x_1=\frac{1}{2}$$

Next, we work with our system.

We subtract the equation number $m-2$ from the equation number $m-1$ to show:

$$x_1+x_2+\cdots + x_{m-2}=1-2(m-1)x_{m-1}$$

Now we add this equation to the equation number $m-1$ and obtain:

$$(m+1)x_1+(m+2)x_2+\cdots + (2m-2)x_{m-2}+(2m-2)x_{m-1}=m-2(m-1)x_{m-1}$$

$$(m+1)x_1+(m+2)x_2+\cdots + (2m-2)x_{m-2}=m-(4m-4)x_{m-1}$$

Now we use the RHS from this equation in the equation number $m$:

$$m-(4m-4)x_{m-1}+(2m-1)x_{m-1}+2mx_m=m$$

Finally we obtain:

$$x_m=\frac{2m-3}{2m}x_{m-1}$$

$$x_1=\frac{1}{2}$$