Prove that $10^{n+k} - 10^{k}$ can be written as a sum of $18k$ perfect (non-zero) squares; for every $n \ge 1,\: k \ge 1$.
Is there a way to prove this without using induction, using elementary school techniques? (induction solution below)
Thanks!
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
If you consider a telescoping sum so obviously correct it's not "induction",$$10^{n+k}-10^n=\sum_{j=0}^{k-1}(10^{n+j+1}-10^{n+j})=\sum_{j=0}^{k-1}9\times10^{n+j},$$so you just need to write $10^{n+j}$ as the sum of two squares. If $n+j$ is odd, multiply $10=1^2+3^2$ by $10^{n+j-1}=(10^{(n+j-1)^2})^2$; if $n+j$ is even it's $\ge2$, so multiply $100=6^2+8^2$ by $10^{n+j-2}=(10^{(n+j)/2-1})^2$.
$\begingroup$
$\endgroup$
I got one solution by induction, for n odd and n even;
E.g. if n is odd, $10^n = 10^{n-1} \times 10 \times (10^{k} - 1)$;
Showing by induction that $10(10^k - 1) = p_{1}^{2} + ... p_{18k}^{2}$:
P(1) : $90 = 9 \times 1 + 9 \times 9$ --> 18 perfect squares
P(2) : $990 = 9 \times 1 + 9 \times 9 + 9 \times 6^{2} + 9\times 8^{2} $--> 36 perfect squares Assuming P(k) true, we prove P(k+2), by replacing 10^k with the sum of squares from P(k) + 1, and rearranging to obtain 18k +36 squares.
And, similarly, for n even (showing that $100 * (10^k - 1)$ can be written as a sum of 18k squares.