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 ?
Best Answer
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.