Can this algebraic problem be solved without observation?

[anemone]

Hi MHB,

I was wondering if this is a very hard problem to solve algebraically, rather than by mere observation.

Problem:

Given

\(\displaystyle \frac{a_1}{2}+\frac{a_2}{3}+...+\frac{a_{2013}}{2014}=\frac{4}{3}\)

\(\displaystyle \frac{a_1}{3}+\frac{a_2}{4}+...+\frac{a_{2013}}{2015}=\frac{4}{5}\)

\(\displaystyle \frac{a_1}{4}+\frac{a_2}{5}+...+\frac{a_{2013}}{2016}=\frac{4}{7}\)

...

\(\displaystyle \frac{a_1}{2014}+\frac{a_2}{2015}+...+\frac{a_{2013}}{4026}=\frac{4}{4027}\)Find

\(\displaystyle \frac{a_1}{3}+\frac{a_2}{5}+...+\frac{a_{2013}}{4027}\)Attempt:

I first started out by using only two terms, $a_1$ and $a_2$ to find the values for each terms and then add one-third to the variable $a_1$ and one-fifth to the variable $a_2$ and I see that

\(\displaystyle \frac{a_1}{3}+\frac{a_2}{5}=\frac{24}{25}=1-\frac{1}{5^2}\)

I then played with three terms, $a_1, a_2$ and $a_3$ and get

\(\displaystyle \frac{a_1}{3}+\frac{a_2}{5}+\frac{a_3}{7}=\frac{48}{49}=1-\frac{1}{7^2}\)

and Et voila, we can conclude that \(\displaystyle \frac{a_1}{3}+\frac{a_2}{5}+...+\frac{a_{2013}}{4027}=1-\frac{1}{4027^2}\)


But I know this is a piece of sloppy working...could someone show me the "real" method to solve this kind of problem? Thanks.

 

[HallsofIvy]

Re: Find a_1/3+a_2/5+..

I wouldn't say it was "hard", just extremely "tedious". You could use a purely "mechanical" algorithm (such as could be programmed into a computer or calculator) to solve 2013 linear equations with 2013 unknowns but it would take a heck of a long time by hand!

 

[anemone]

Re: Find a_1/3+a_2/5+..

I see...thanks for the reply, HallsofIvy!

 

[Opalg]

Re: Find a_1/3+a_2/5+..

Hi MHB,
I was wondering if this is a very hard problem to solve algebraically, rather than by mere observation.
Problem:
Given
\(\displaystyle \frac{a_1}{2}+\frac{a_2}{3}+...+\frac{a_{2013}}{2014}=\frac{4}{3}\)
\(\displaystyle \frac{a_1}{3}+\frac{a_2}{4}+...+\frac{a_{2013}}{2015}=\frac{4}{5}\)
\(\displaystyle \frac{a_1}{4}+\frac{a_2}{5}+...+\frac{a_{2013}}{2016}=\frac{4}{7}\)
...
\(\displaystyle \frac{a_1}{2014}+\frac{a_2}{2015}+...+\frac{a_{2013}}{4026}=\frac{4}{4027}\)
Find
\(\displaystyle \frac{a_1}{3}+\frac{a_2}{5}+...+\frac{a_{2013}}{4027}\)
Attempt:
I first started out by using only two terms, $a_1$ and $a_2$ to find the values for each terms and then add one-third to the variable $a_1$ and one-fifth to the variable $a_2$ and I see that
\(\displaystyle \frac{a_1}{3}+\frac{a_2}{5}=\frac{24}{25}=1-\frac{1}{5^2}\)
I then played with three terms, $a_1, a_2$ and $a_3$ and get
\(\displaystyle \frac{a_1}{3}+\frac{a_2}{5}+\frac{a_3}{7}=\frac{48}{49}=1-\frac{1}{7^2}\)
and Et voila, we can conclude that \(\displaystyle \frac{a_1}{3}+\frac{a_2}{5}+...+\frac{a_{2013}}{4027}=1-\frac{1}{4027^2}\)
But I know this is a piece of sloppy working...could someone show me the "real" method to solve this kind of problem? Thanks.

The system of equations
$$\begin{aligned}\frac{a_1}{2}+\frac{a_2}{3}+ … +\frac{a_n}{n+1} &=\frac{4}{3}\\ \frac{a_1}{3}+\frac{a_2}{4}+…+\frac{a_{n}}{n+2} &=\frac{4}{5}\\ \frac{a_1}{4}+\frac{a_2}{5}+…+\frac{a_{n}}{n+3} &=\frac{4}{7} \\ &\vdots\\ \frac{a_1}{n+1}+\frac{a_2}{n+2}+…+\frac{a_{n}}{2n} &=\frac{4}{2n+1} \end{aligned}$$
can be written in matrix form as $H_na = 4k$, where $a$, $k$ are the column vectors with coordinates $(a_1,a_2,\ldots,a_n)$, $\bigl(\frac13,\frac15,\ldots,\frac1{2n+1}\bigr)$, and $H_n$ is the $n\times n$ Hilbert matrix $$H_n = \begin{bmatrix} \frac12&\frac13&\frac14&\ldots&\frac1{n+1}\\ \frac13&\frac14&\frac15&\ldots&\frac1{n+2}\\ \frac14&\frac15&\frac16&\ldots&\frac1{n+3}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ \frac1{n+1}&\frac1{n+2}&\frac1{n+3}&\ldots&\frac1{2n} \end{bmatrix}.$$ Strictly speaking, $H_n$ is a variant of the Hilbert matrix. The standard Hilbert matrix starts with $1$ rather than $\frac12$ in the top left corner.The problem in this thread is to find the inner product $\langle a,k\rangle = \sum_{i=1}^na_ik_i$ when $n=2013.$ HallsofIvy correctly comments that this is "just" a question of solving a system of linear equations. But the Hilbert matrix is notoriously ill-conditioned for such calculations, and I suspect that a computer would be hard put to come up with an exact solution to a system containing so many different fractions. Unless I am overlooking some clever technique, this is a very tricky problem, and anemone has done well to spot that the answer should be $1-\frac1{(2n+1)^2}.$As Halloween approaches, this is a good time to give a link to Man-Duen Choi's fascinating paper Tricks or treats with the Hilbert matrix. All the ideas in this comment come from Choi's paper. The only difference is that Choi deals with the standard Hilbert matrix, and the numbers have to be changed for the variant Hilbert matrix.The (variant) Hilbert matrix is invertible, so the equation $H_na = 4k$ can be written as $a = 4H_n^{-1}k$, and the inner product $\langle a,k\rangle$ then becomes $4\langle H_n^{-1}k,k\rangle$. That enables us to avoid having to find the vector $a$ at all, but at the cost of having to find $H_n^{-1}$. For $n=2,3,4$ the inverses are $$ H_2^{-1} = \begin{bmatrix} 18&-24\\ -24&36\end{bmatrix}, \qquad H_3^{-1} = \begin{bmatrix} 72&-240&180 \\ -240&900&-720 \\ 180&-720&600\end{bmatrix}, \qquad H_4^{-1} = \begin{bmatrix} 200 &-1200 &2100 &-1120 \\ -1200 &8100 &-15120 &8400 \\ 2100 &-15120 &29400 &-16800 \\ -1120 & 8400 &-16800 & 9800 \end{bmatrix}.$$ Here you see the first surprise that the Hilbert matrix has to offer: its inverse consists entirely of integers! The general formula for the $(i,j)$-entry in $H_n^{-1}$ is $$\bigl(H_n^{-1}\bigr)_{i\,j} = \frac{(-1)^{i+j}ij}{i+j}{n\choose i}{n\choose j}{n+i\choose i}{n+j\choose j}. \qquad(1)$$
If you use those values for the elements of $(H_n)^{-1}$ then you find that $$4\langle H_n^{-1}k,k\rangle = \sum_{i,j=1}^n \frac{(-1)^{i+j}ij}{(2i+1)(2j+1)(i+j)}{n\choose i}{n\choose j}{n+i\choose i}{n+j\choose j}. \qquad(2)$$ That ought to reduce to $1-\frac1{(2n+1)^2}.$ But it looks like a very hard double summation, and I have no idea how to do it.A useful property of $H_n^{-1}$ is that it factorises as a product $H_n^{-1} = X_n^*X_n$, where $X_n$ is an upper -triangular matrix so that its transpose $X_n^*$ is lower-triangular. For $n=2,3,4$ these factorisations look like $$\begin{bmatrix} 18&-24\\ -24&36\end{bmatrix} = \begin{bmatrix} \sqrt2 & -2\sqrt4 \\ 0 & 3\sqrt4 \end{bmatrix} \begin{bmatrix} \sqrt2 & 0 \\ -2\sqrt4 & 3\sqrt4 \end{bmatrix}, \qquad \begin{bmatrix} 72&-240&180 \\ -240&900&-720 \\ 180&-720&600\end{bmatrix} = \begin{bmatrix} \sqrt2 & -2\sqrt4 & 3\sqrt6 \\ 0 & 3\sqrt4 & -12\sqrt6 \\ 0&0& 10\sqrt6 \end{bmatrix} \begin{bmatrix} \sqrt2 & 0 &0 \\ -2\sqrt4 & 3\sqrt4 &0 \\ 3\sqrt6 & -12\sqrt6 & 10\sqrt6 \end{bmatrix},$$ $$\begin{bmatrix} 200 &-1200 &2100 &-1120 \\ -1200 &8100 &-15120 &8400 \\ 2100 &-15120 &29400 &-16800 \\ -1120 & 8400 &-16800 & 9800\end{bmatrix} = \begin{bmatrix} \sqrt2 & -2\sqrt4 & 3\sqrt6 & -4\sqrt8 \\ 0 & 3\sqrt4 & -12\sqrt6 & 30\sqrt8\\ 0&0& 10\sqrt6 & -60\sqrt8 \\ 0&0&0& 35\sqrt8\end{bmatrix} \begin{bmatrix} \sqrt2 & 0 &0&0 \\ -2\sqrt4 & 3\sqrt4 &0&0 \\ 3\sqrt6 & -12\sqrt6 & 10\sqrt6 &0 \\ -4\sqrt8 & 30\sqrt8 & -60\sqrt8 & 35\sqrt8 \end{bmatrix}$$ (I have left $\sqrt4$ without simplifying it in order to make the pattern clearer). The general formula for the $(i,j)$-element of $X_n$ is $$(X_n)_{i\,j} = (-1)^{i+j}\sqrt{2i}\frac j{i+j}{i\choose j}{i+j \choose j}\qquad(3)$$ for $i\geqslant j$, and $(X_n)_{i\,j} = 0$ for $i<j$. Notice that $(X_n)_{i\,j}$ does not depend on $n$. This means that each matrix $X_n$ is embedded as the top left part of $X_{n+1}$. As Choi points out, this can be extremely useful in proofs by induction.Coming back to the expression that we want to evaluate, we can now write $\langle a,k\rangle = 4\langle H_n^{-1}k,k\rangle = 4\langle X_n^*X_nk,k\rangle = 4\langle X_nk,X_nk\rangle = 4\|X_nk\|^2$. That last expression is $4$ times the sum of the squares of the coordinates of $X_nk$. The $i$th coordinate of $X_nk$ is $$\sum_{j=1}^i (-1)^{i+j}\sqrt{2i}\frac j{(i+j)(2j+1)}{i\choose j}{i+j \choose j}. \qquad(4)$$ In the cases when $n=2,\;3$ and $4$, that sum (4) is equal to $\dfrac{(-1)^{i-1}\sqrt{2i}}{4i^2-1}$. If that holds in general, then it follows that $$\langle a,k\rangle = \sum_{i=1}^n\dfrac{8i}{(4i^2-1)^2}.\qquad(5)$$ But $$\dfrac{8i}{(4i^2-1)^2} = \dfrac{8i}{(2i-1)^2(2i+1)^2} = \dfrac1{(2i-1)^2} - \dfrac1{(2i+1)^2}.$$ Thus the series in (5) becomes a telescoping sum, equal to $1-\frac1{(2n+1)^2}$, as we wanted.What has been achieved by all this? Unfortunately, very little. To complete the proof that $\langle a,k\rangle = 1-\frac1{(2n+1)^2}$, it would be necessary to sum either the double series (2) (which seems impossibly hard), or the series (4). That at least only involves summation over one index, but I still do not see how to sum it.

 

[anemone]

Re: Find a_1/3+a_2/5+..

Hi Opalg,

Thank you so much for your reply, and even though we haven't "solved" this problem using your matrices approach, I feel I owe you a great deal of gratitude since I can tell you have had spent a great deal of time trying to solve this hard problem and for this, I am very grateful to you for your help!

Words cannot aptly express my gratitude to you, Mr. Opalg!:)

 

[issacnewton]

Re: Find a_1/3+a_2/5+..

\(\displaystyle \frac{a_1}{3}+\frac{a_2}{5}=\frac{24}{25}=1-\frac{1}{5^2}\)

I then played with three terms, $a_1, a_2$ and $a_3$ and get

\(\displaystyle \frac{a_1}{3}+\frac{a_2}{5}+\frac{a_3}{7}=\frac{48}{49}=1-\frac{1}{7^2}\)

Hello

How did you get these two equations. I am confused.

 

[anemone]

Re: Find a_1/3+a_2/5+..

Hello

How did you get these two equations. I am confused.

Hi IssacNewton,

Let's say we want to limit the number of variables in the given problem down to only two, namely $a_1$ and $a_2$, we then have the following system:

\(\displaystyle \frac{a_1}{2}+\frac{a_2}{3}=\frac{4}{3}\)

\(\displaystyle \frac{a_1}{3}+\frac{a_2}{4}=\frac{4}{5}\)

and this is a system of linear equations and I believe you know how to solve for the rest!:)

 

[issacnewton]

Re: Find a_1/3+a_2/5+..

Thanks...it now makes complete sense. (Music)