Add the numbers in a 9x9 multiplication Table
Kaz Kylheku
643-408-1753 at kylheku.com
Fri Jan 3 18:12:18 EST 2025
On 2025-01-03, HenHanna <HenHanna at 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 at mstdn.ca
More information about the Python-list
mailing list