XPost: rec.puzzles, comp.lang.python
On 2025-01-03, HenHanna <
HenHanna@dev.null> wrote:
On Thu, 2 Jan 2025 10:54:02 +0000, yeti wrote:
https://oeis.org/A000537 ?
Sum of first n cubes; or n-th triangular number squared.
0, 1, 9, 36, 100, 225, 441, 784, 1296, 2025, 3025, 4356, 6084, 8281,
11025, 14400, 18496, 23409, 29241, 36100, 44100, 53361, 64009, 76176,
90000, 105625, 123201, 142884, 164836, 189225, 216225, 246016, 278784, 314721, 354025, 396900, 443556, 494209, 549081
Thank you... It's not obvous to me why
Sum of (consecutive) cubes would be a Square number.
Base case:
1^3 is a square number.
Inductive hypothesis:
Suppose that the sums of 1^3 through n^3 are a square number.
What happens when we add (n+1)^3?
In other words:
sum{1, n, n^3} = k * k (for some positive integer k)
What are we adding to this k * k?
(n+1)^3 = n^3 + 3n^2 + 3n + 1
We have to show that adding this forumla to some k * k
produces (k + m) * (k + m) for some positive integer m.
When we take a k * k square and add m to the edges, we get
k^2 + 2km + m^2. In other words, the newly added area beyond the
original k^2 consists of two k * m quadrangles and an m^2 square.
Thus, it follows that the (n+1)^3 formula must be expressible in this
form: 2km + m^2.
Each successive cube must be adding area to a previous k*k square to
make a larger square, by adding m to the edge, which results in an new
additional area of 2km + m^2. (Of course the k and m are different
for each new cube.)
n^3 + 3n^2 + 3n + 1 = m^2 + 2km
For instance, 27 is equal to { k = 3, m = 3 } 3^2 + 2*3*3.
On in the n = 7 case, 441 going to 784 (+ 343) we have { k = 21, m = 7 }:
343 = 7*7*7 = 7*7 + 2*21*7
A pattern is emerging that m is the root of the cube; in
other words that m = n + 1. Thus:
n^3 + 3n^2 + 3n + 1 = (n+1)^2 + 2k(n + 1)
n^3 + 3n^2 + 3n + 1 = n^2 + 2n + 1 + 2k(n + 1)
Get k by itself:
n^3 + 2n^2 + 3n + 1 = 2n + 1 + 2k(n + 1)
n^3 + 2n^2 + n + 1 = 1 + 2k(n + 1)
n^3 + 2n^2 + n = 2k(n + 1)
n^3 + 2n^2 + n = 2k
------
n + 1
We need to do long polynomial division to work out this
fraction on the left:
n^2 + n
_____________________
n + 1 | n^3 + 2n^2 + n + 0
n^2 + n^2
----------
n^2 + n + 0
n^2 + n
---------
0 + 0
This is the key: the division is exact!
2k = n^2 + n = n(n + 1)
k = n(n + 1)/2
which we know is an integer!
So we know that each new cube (n+1)^3 is
expressible in the form of:
m^2 + 2km
if we identify k, m as:
m = n + 1, and
k = n(n + 1)/2 .
What we have to show is that k is the correct square value.
If k is the correct original square, then we have proved it;
because k^2 + 2m is the correct quantity to take the k square
to the k + m square.
We could use a separate, parallel induction to prove this.
Note that the formula k = n(n + 1)/2 is just the summation formula
for consecutive integers from 1 to n. We can prove that
the successive squares in the squares of these sums:
sum(1..1)^2 = 1
sum(1..2)^2 = 3^2 = 9
sum(1..3)^2 = 6^2 = 36
sum(1..4)^2 = 10^2 = 100
So it's obvious by inspection that we have the correct k formula,
and we can prove it more formally.
Conclusion:
Since we have a base case, and true inductive hypothesis, the result
holds for all n.
The key insights are that
1. the sequence values are the squares of consecutive integer sums;
i.e. the squares of successive k-s, where k = n(n+1)/2.
2. each cube value added to the previous sequence value
is expressible in the form m^2 + 2km, which has the right
shape to preserve the square property, and that with some
algebra we can identify m as m = n + 1.
--
TXR Programming Language:
http://nongnu.org/txr
Cygnal: Cygwin Native Application Library:
http://kylheku.com/cygnal
Mastodon: @
Kazinator@mstdn.ca
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)