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