# Triangle table: Moscow MO 1958 triangular table with numbers

In the following triangular table $$0\,\, 1 \,\,2\,\, . . . . . . . . . . . . . . . 1957 \,\,1958$$ $$\,\,\,\,1 \,\,3 \,\,5\,\, . . . . . . . . . . . . \,\,\,\,3915$$ $$. . . . . . . . . . . .$$ each number (except for those in the upper row) is equal to the sum of the two nearest numbers in the row above. Prove that the lowest number is divisible by $$1958$$.

My progress: Well, $$1958$$ surely isn't special. So let's prove for any $$a_1,a_2,a_3,\dots a_n$$ triangular table.

So we have $$a_1~~a_2~~a_3~~a_4\dots \dots~~a_n$$ $$\downarrow$$ $$(a_1+a_2)~~(a_2+a_3)~~(a_3+a_4)~~(a_4+a_5)\dots \dots ~~(a_{n-1}+a_n)$$ $$\downarrow$$ $$(a_1+2a_2+a_3)~~(a_2+2a_3+a_4)\dots\dots ~~( a_{n-2}+2a_{n-1}+a_n)$$ $$\downarrow$$ $$(a_1+3a_2+3a_3+a_4)~~(a_2+3a_3+3a_4+a_5)\dots \dots$$ $$\downarrow$$ $$(a_1+4a_2+6a_3+4a_4+a_5)~~ (a_2+4a_3+6a_4+4a_5+a_6)\dots$$ $$\downarrow$$ $$(a_1+5a_2+10a_3+10a_4+5a_5+a_6)\dots$$ $$\vdots$$

Now, we only care about the first term of each row. In the last row of the table, there is only one term.

Now, one can notice the pattern in the first terms, in general (proovable by induction) they are of the form $$(a_1+\binom{k}{1}a_2+\dots + \binom {k}{2}a_{k-1}+\binom{k}{k-1}a_k+a_{k+1}).$$

So the last row's term will be $$(a_1+\binom{n-1}{1}a_2+ \binom{n-1}{2}a_3+\dots + \binom{n-1}{n-2}a_{n-1}+a_n).$$

then we have $$a_1=0,a_n=1958$$ Here, we have $$\binom{1957}{1}1+ \binom{1957}{2}2+\dots + \binom{1957}{1956}1957+1958.$$

So we have to show that $$1958|\binom{1957}{1}1+ \binom{1957}{2}2+\dots + \binom{1957}{1956}1957$$

How to proceed ?

• Commented Aug 3, 2021 at 14:52
• Something seems off... you have $\binom{1957}{1}1+\binom{1957}{2}2$ where the bottom of the binomial coefficient is the same as the coefficient next to it... but then you have $\binom{1957}{1956}1957$ where the bottom of the binomial coefficient is one less than the coefficient next to it. Commented Aug 3, 2021 at 14:57
• You should check and verify all of the numbers involved. In the end, you will likely end up using either the full identity that Aravind linked to (that $\sum\limits_{r=0}^nr\binom{n}{r}=n2^{n-1}$) or you can use a more direct answer involving $\binom{n}{k}k = n\binom{n-1}{k-1}$ Commented Aug 3, 2021 at 15:00
• yes, i too think. I hope someone can point out where i made the loophole :( Commented Aug 3, 2021 at 15:13

That's all good but take into account that $$n$$ is $$1959$$ so you get $$\binom{1958}{1}1+ \binom{1958}{2}2+\dots + \binom{1958}{1957}1957 + \color{blue}{ \binom{1958}{1958} 1958}$$ which of course just counts the total number of elements over all subsets of $$\{1,\dots,1958\}$$ which is $$2^{1958-1}1958$$ when seeing how many times each element appears.