It is dividable! - 09/05/2013

[showmyiq]

\begin{equation}
\text{If n is an odd natural number, then the number } \\
a_k = 1^n + 2^n + \cdots + k^n \\
\text{is dividable by } \frac {1} {2}k(k+1) \text{ for every natural number k}\\
\end{equation}

Can you prove that?

[showmyiq]

The puzzle is cracked by Sergey Sokolov via Facebook!

I really liked his approach, I hope you enjoy it too.

We have:

\begin{equation}
a_{n,k} = 1^n + 2^n + \cdots + k^n \\
\text{Let's define such } b_{n,k,m} \text{ that} \\
b_{n,k,m} = m^n + (k-m)^n\\
b_{n,k,m} = m^n + [{n \choose 0}k^nm^0 - {n \choose 1}k^{n-1}m^1 + {n \choose 2}k^{n-2}m^2 ] - \cdots - \\
{n \choose n-2}k^{2}m^{n-2} + {n \choose n-1}k^{1}m^{n-1} - {n \choose n}k^{0}m^{n}] \\
\text{The last element is with sign MINUS because n is an odd number}\\
b_{n,k,m} = m^n + {n \choose 0}k^nm^0 - {n \choose 1}k^{n-1}m^1 + {n \choose 2}k^{n-2}m^2 ] - \cdots - \\
{n \choose n-2}k^{2}m^{n-2} + {n \choose n-1}k^{1}m^{n-1} - m^{n} \\
b_{n,k,m} = {n \choose 0}k^nm^0 - {n \choose 1}k^{n-1}m^1 + {n \choose 2}k^{n-2}m^2 ] - \cdots - \\
{n \choose n-2}k^{2}m^{n-2} + {n \choose n-1}k^{1}m^{n-1} \\
b_{n,k,m} = k*\delta \text{ , for some random natural number } \delta
\end{equation}
As we can see b is dividable by k, no matter the values of n(odd n's),k or m.
Now let’s calculate some b’s for specific m’s.

\begin{equation}
b_{n,k,0} = 0^n + (k-0)^n = 0 + k^n = k^n \\
b_{n,k,1} = 1^n + (k-1)^n \\
b_{n,k,2} = 2^n + (k-2)^n \\
\cdots \\
b_{n,k,m} = m^n + (k-m)^n \\
\text{Therefore we can construct a's with b's} \\
\color{red}{\text{1st case: k is and odd number}} \\
a_{n,k} = b_{n,k,0} + b_{n,k,1} + \cdots + b_{n,k,{\frac{k-1}{2}}} \\
\text{You can see that such representation is adequate and correct}\\
\text{For example if k=11, we will have:} \\
a_{n,11} = b_{n,11,0} + b_{n,11,1} + \cdots + b_{n,11,{\frac{11-1}{2}}}\\
a_{n,11} = b_{n,11,0} + b_{n,11,1} + \cdots + b_{n,11,5}\\
a_{n,11} = 11^n + [1^n + 10^n] + [2^n + 9^n] + [3^n + 8^n] + [4^n + 7^n] + [5^n + 6^n]\\
a_{n,11} = 1^n + \cdots + 11^n \\
\text{So we can conclude that for some natural number }\epsilon,\\
a_{n,k} = b_{n,k,0} + b_{n,k,1} + \cdots + b_{n,k,{\frac{k-1}{2}}} = k*\epsilon \\
\text{Therefore }a_{n,k} \text{ is dividable by } k \text{, for k - odd number}\\
\color{red}{\text{2nd case: k is and even number}} \\
a_{n,k} = b_{n,k,0} + b_{n,k,1} + \cdots + b_{n,k,{\frac{k}{2}}} - (\frac{k}{2})^n \\
\text{You can see that such representation is adequate and correct}\\
\text{For example if k=10, we will have:} \\
a_{n,10} = b_{n,10,0} + b_{n,10,1} + \cdots + b_{n,10,{\frac{10}{2}}} - (\frac{10}{2})^n \\
a_{n,10} = b_{n,10,0} + b_{n,10,1} + \cdots + b_{n,10,5} - 5^n \\
a_{n,10} = 10^n + [1^n + 9^n] + [2^n + 8^n] + [3^n + 7^n] + [4^n + 6^n] + [5^n + 5^n] - 5^n \\
a_{n,10} = 10^n + [1^n + 9^n] + [2^n + 8^n] + [3^n + 7^n] + [4^n + 6^n] + 5^n \\
a_{n,10} = 1^n + \cdots + 10^n \\
\text{So we can conclude that for some natural number }\vartheta,\\
a_{n,k} = b_{n,k,0} + b_{n,k,1} + \cdots + b_{n,k,{\frac{k}{2}}} - (\frac{k}{2})^n = \frac{k}{2}*\vartheta \\
\text{Therefore }a_{n,k} \text{ is dividable by } \frac{k}{2} \text{, for k - even number} \\
\end{equation}
Ok, so far – so good. Now, let’s use another approach to construct a’s from b’s.

\begin{equation}
b_{n,k+1,1} = 1^n + (k+1-1)^n=1^n + k^n\\
b_{n,k+1,2} = 2^n + (k+1-2)^n = 2^n + (k-1)^n\\
\cdots \\
b_{n,k+1,m} = m^n +(k+1-m)^n\\
\color{red}{\text{1st case: k - an odd number}}\\
a_{n,k}=b_{n,k+1,1} + b_{n,k+1,2} + \cdots + b_{n,k+1,\frac{k+1}{2}} - {\frac{k+1}{2}}^n\\
\text{You can again substitute some odd number k to test the equation.}\\
\text{So we can conclude that for some natural number }\zeta,\\
a_{n,k}=b_{n,k+1,1} + b_{n,k+1,2} + \cdots + b_{n,k+1,\frac{k+1}{2}} - {\frac{k+1}{2}}^n = \frac{k+1}{2}*\zeta \\
\text{Therefore } a_{n,k} \text{ is dividable by } \frac{k+1}{2} \text{, for k - odd number} \\
\color{red}{\text{2nd case: k - an even number}}\\
a_{n,k}=b_{n,k+1,1} + b_{n,k+1,2} + \cdots + b_{n,k+1,\frac{k}{2}}\\
\text{You can again substitute some even number k to test the equation.}\\
\text{So we can conclude that for some natural number }\xi,\\
a_{n,k}=b_{n,k+1,1} + b_{n,k+1,2} + \cdots + b_{n,k+1,\frac{k}{2}} = (k+1)*\xi \\
\text{Therefore } a_{n,k} \text{ is dividable by } k+1 \text{, for k - even number} \\
\end{equation}
Let’s now combine the 1st and 2nd cases from first construction of a’s and second constructions of a’s.

\begin{equation}
\text{Therefore }a_{n,k} \text{ is dividable by } k \text{, for k - odd number}\\
\text{Therefore } a_{n,k} \text{ is dividable by } \frac{k+1}{2} \text{, for k - odd number} \\
\text{Therefore }a_{n,k} \text{ is dividable by } \frac{k}{2} \text{, for k - even number} \\
\text{Therefore } a_{n,k} \text{ is dividable by } k+1 \text{, for k - even number} \\
\color{green}{\text{Let's combine the statements now}}\\
\text{Therefore }a_{n,k} \text{ is dividable by } k*\frac{k+1}{2} \text{, for k - odd number}\\
\text{Therefore }a_{n,k} \text{ is dividable by } k*\frac{k+1}{2} \text{, for k - even number}\\
\color{green}{\text{Let's combine the statements again}}\\
\text{Therefore }a_{n,k} \text{ is dividable by } \frac{k*(k+1)}{2} \text{, for any k}\\
\color{green}{\text{And we have just proved the statement!}}\\
\color{green}{\text{Excellent work, Sergey!}}\\
\end{equation}

[snsokolov]

As usual - great job converting this to latex. Just two notes here:

>As we can see b is dividable by k, no matter the values of n,k or m.

I'd add that n must be an odd number.

>Therefore an,k is dividable by k, for k - odd numberTherefore an,k is dividable by (k+1)/2, for k - odd number. Let's combine the statements now

We forgot to mention one important thing. k and k+1 cannot have any common dividers other than 1. That is why if an,k is dividable by both k and (k+1)/2 we can say that it is also dividable by k(k+1)/2.

[showmyiq]

Thank you for your corrections.
I have updated the section with n and now the statement is fulfilled with only odd n’s.

About the second update:

\begin{equation}
\text{Let's define k as an odd number} \\
\text{Does k and (k+1)/2 have common divider?}\\
\text{Let's say they do have common divider } \omega \text{, different from 1}\\
k = \omega*A \text{, for some natural number A}\\
\frac {k+1} {2} = \omega*B\text{, for some natural number B}\\
k=2*l + 1 \text{, for some natural number l}\\
2*l + 1 = \omega*A \\
\frac {2l + 1 +1} {2} = l+ 1 = \omega*B \\
\omega*A = 2*l + 1 = l + \underbrace{l + 1}_{\text{equal to } \omega*B} = l + \omega*B \\
\text{Therefore, l is dividable by } \omega \\
\text{But l+1 is dividable by } \omega \text{ too!}\\
Contradiction!
\end{equation}
We can conclude that – k and (k+1)/2 for any odd number k, doesn’t have common divider different by 1.

\begin{equation}
\text{Let's define k as an even number} \\
\text{Does k/2 and k+1 have common divider?}\\
\text{Let's say they do have common divider } \omega\\
\frac {k}{2} = \omega*A \text{, for some natural number A}\\
k+1 = \omega*B\text{, for some natural number B}\\
k=2*l \text{, for some natural number l}\\
\frac{2l}{2} = l =\omega*A \\
2l+1 = \omega*B \\
\omega*B = 2*l + 1 = 2*\underbrace{l}_{\text{equal to } \omega*A} + 1= 2*\omega*A + 1\\
\text{Therefore, 1 is dividable by } \omega \\
\text{Therefore, } 1=\omega. \\
\end{equation}
We can conclude that – k/2 and k+1 for any even number k, doesn’t have common divider different by 1.