Series and Induction

   6   12     20    30     42    

                6      8      10     12

                    2       2       2

In the last case, the numbers in my first two rows of differences are not all the same, but in the third row of differences, the differences are all the same. Because the difference is 2 after three rounds of subtracting in this fashion, the equation that I will set as my conjecture will be of degree 3, in the form Sn = an3 + bn2 + cn + d.  There are 4 unknowns, so I set up 4 equations:

S1 = a + b + c + d which we know equals 2 (from part a)

S2 = a23 + b22 + 2c + d

     = 8a + 4b + 2c + d = 8

S3 = a33 + b32 + 3c + d

     = 27a + 9b + 3c + d = 20

S4 = a43 + b42 + 4c + d

     = 64a + 16b + 4c + d = 40

These values were entered into the GDC as matrix A  and Band it was determined by reduced row echelon form that a =, b = 1, c =, and d = 0.         

Therefore, Sn = n3 + n2 + n 

Sn = a1 + a2 + a3 + a4 + … + an = 1 x 2 + 2 x 3 + 3 x 4 + … + n(n+1) = =  

     =

Thus, = Sn -

We know that = 1 + 2 + 3 + … + n =  and that  Sn =  n3 + n2 + n, so plug these values in and:

= Sn - = n3 + n2 + n -  =  =

Thus, my conjecture is that: =

Check:

n = 1;  = 12 = 1 

now try this with the above equation… = 1 [it fits!]

n = 2; = 12 + 22 = 5

now with the above equation… = 5 [it fits!]

n = 3;  = 12 + 22 + 32  = 14

now with the above equation… = 14 [it fits!]

Let’s check if this conjecture works all other values of n using an induction proof:

Step 1 Assume the conjecture to be true for n = 1

As shown above,

= 12 = = 1

Step 2 Assume the conjecture to be true for n = k        

 So =  

Step 3 Observe for if n = k + 1

= 1 + 22 + 32 + ... + k2 + (k+1)2 which, according to the formula, should equal

 = + (k+1)2 = + (k+1)2 =

                 = = =

 is equal to the equation above, so =  is true.

3. Consider Tn = 1x2x3 + 2x3x4 + 3x4x5 + … + n(n+1)(n+2)

a) Determine several values of Tk including T1, T2, T3, …, T6 

T1 = a1 = 1 x 2 x 3= 6        

T2 = a1 + a2 = T1 + a2 = 6 + 2 x 3 x 4 = 30

T3 = a1 + a2 + a3 = T2 + a3 = 30 + 3 x 4 x 5 = 90

T4 = a1 + a2 + a3 + a4 = T3 + a4 = 90 + 4 x 5 x 6 = 210

T5 = = a1 + a2 + a3 + a4 + a5 = T4 + a5 = 210 + 5 x 6 x 7 = 420

T6 = a1 + a2 + a3 + a4 + a5 + a6 = T5 + a6 = 420 + 6 x 7 x 8 = 756

T7 = a1 + a2 + a3 + a4 + a5 + a6 + a7= T6 + a7 = 756 + 7 x 8 x 9 = 1260

It seems that for every increasing value of k, the sum of the previous numbers plus the new number yields the new sum.

b) Thus, the conjecture is that: Tk = Tk-1 + ak

c) Prove conjecture by induction:

Step 1 Assume the conjecture to be true for n = 1

As shown above,

T1 = a1 = 1 x 2 x 3= 6

T2 = a1 + a2 = 6 + 2 x 3 x 4 = 30

T3 = a1 + a2 + a3 = 30 + 3 x 4 x 5 = 90

So Tn = Tn-1 + an

Step 2 Assume the conjecture to be true for n = k (done in part a of 2)

   So Tk = T1 + T2 + T3 + … + Tk = Tk-1 + ak

   Tk = Tk-1 + ak

Step 3 Observe for if n = k + 1

According to conjecture it should be: Tk+1 = Tk + ak+1

So substitute Tk-1 + ak for Tk (in step 2):

Tk+1 = (Tk-1 + ak) + ak+1 = Tk-1 + ak + ak(a1)

d) Using the above result, calculate 13 + 23 + 33 + 43 + … + n3

Taking the sums of terms a1= 1x2x3, a2 = 2x3x4, a3 = 3x4x5, a4 = 4x5x6… from part a, it can be seen that, as it was with the differences of squares, the differences of consecutive terms (cubes) turns out to be a common number. Except this time, this number was 6 after 4 rounds of subtracting in this fashion:

 6    30     90       210      420      756      1260

    24    60    120     210       336      504

           36    60       90       126      168  

               24     30      36        42

                  6        6        6

The equation that I will set as my conjecture will be of degree 4, in the form Sn = an4 + bn3 + cn2 + dn + e.  There are 5 unknowns, so I set up 5 equations:

T1 = a + b + c + d + e which we know equals 6 (from part a)

T2 = a24 + b23 + c22 + 2d + e

     =  16a +8b + 4c + 2d + e = 30

T3 = a34 + b33 + c32 + 3d + e

     = 81a + 27b + 9c + 3d + e = 90

T4 = a44 + b43 + c42 + 4d + e

     = 256a + 64b + 16c + 4d + e = 210

T5 = a54 + b53 + c52 + 5d + e

     = 625a + 125b + 25c + 5d + e = 420

These values were entered into the GDC as matrix A  and Band it was determined by reduced row echelon form that a =, b = , c = , d = , and e = 0.  

Therefore, Tn = n4 + n3 + n2 +n 

Tn = a1 + a2 + a3 + a4 + … + an = Tn = 1x2x3 + 2x3x4 + 3x4x5 + … + n(n+1)(n+2)      

     ==  

     =

Thus, = Tn –

We know that =  so = = and that

=2+4+6+8+…+2n can be rewritten by factoring out the 2 to make it 2(1+2+3+…+n). We    

already know 1+2+3+…+n= so, 2 times  becomes simply n(n+1). Also, we  

know that Tn = n4 + n3 - n2 +n so plug these values in and:

= Tn – = n4 + n3 + n2 +n – – n(n+1)

          =  = = =

Thus, my conjecture is that: =

Check:

n = 1; = 13 = 1

now try this with the above equation… = 1 [it fits!]

n = 2; = 13 + 23 = 9

now with the above equation… = 9 [it fits!]

n = 3; = 13 + 23 + 33 = 36

now with the above equation… = 36 [it fits!]

Let’s check if this conjecture works all other values of n using an induction proof:

Step 1 Assume the conjecture to be true for n = 1

As shown above,

= 13 = = 1

Step 2 Assume the conjecture to be true for n = k        

 So =  

Step 3 Observe for if n = k + 1

= 13 + 23 + 33 + ... + k3 + (k+1)3 which, according to the formula, should equal

  = + (k+1)3 = + (k+1)3 =

                 == 

 is equal to the equation above, so =  is true.

4. Consider Un = 1x2x3x4 + 2x3x4x5 + 3x4x5x6 + … + n(n+1)(n+2)(n+3)

a) Determine several values of Uk including U1, U2, U3, …, U6 

U1 = a1 = 1 x 2 x 3 x 4 = 24        

U2 = a1 + a2 = U1 + a2 = 24 + 2 x 3 x 4 x 5 = 144

U3 = a1 + a2 + a3 = U 2 + a3 = 144 + 3 x 4 x 5 x 6 = 504

U4 = a1 + a2 + a3 + a4 = U 3 + a4 = 504 + 4 x 5 x 6 x 7 = 1344

U5 = = a1 + a2 + a3 + a4 + a5 = U 4 + a5 = 1344 + 5 x 6 x 7 x 8 = 3024

U6 = a1 + a2 + a3 + a4 + a5 + a6 = U 5 + a6 = 3024 + 6 x 7 x 8 x 9 = 6048

U7 = a1 + a2 + a3 + a4 + a5 + a6 + a7 = U 6 + a7 = 6048 + 7 x 8 x 9 x 10 = 11088

U8 = a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 = U 7 + a8 = 11088 + 8 x 9 x 10 x 11 = 19008

It seems that for every increasing value of k, the sum of the previous numbers plus the new number yields the new sum.

b) Thus, the conjecture is that: Uk = Uk-1 + ak

c) Prove conjecture by induction:

Step 1 Assume the conjecture to be true for n = 1

As shown above,

U1 = a1 = 1 x 2 x 3 x 4 = 24

U2 = a1 + a2 = T1 + a2 = 24 + 2 x 3 x 4 x 5 = 144

U3 = a1 + a2 + a3 = T2 + a3 = 144 + 3 x 4 x 5 x 6 = 504

So Un = Un-1 + an

Step 2 Assume the conjecture to be true for n = k (done in part a of 2)

   So Uk = U1 + U2 + U3 + … + Uk = Uk-1 + ak

   Uk = Uk-1 + ak

Step 3 Observe for if n = k + 1

According to conjecture it should be: Uk+1 = Uk + ak+1

So substitute Uk-1 + ak for Uk (in step 2):

Uk+1 = (Uk-1 + ak) + ak+1 = Uk-1 + ak + ak(a1)

d) Using the above result, calculate 14 + 24 + 34 + 44 + … + n4

Taking the sums of terms a1= 1x2x3x4, a2 = 2x3x4x5, a3 = 3x4x5x6, a4 = 4x5x6x7… from #5, it can be seen that, as it was with the differences of cubes and squares, the differences of consecutive terms to the fourth power turns out to be a common number. Except this time, this number was 24 after 5 rounds of subtracting in this fashion:

 24    144     504     1344       3024        6048       11088      19008

     120    360     840      1680        3024        5040        7920

              240    480     840         1344        2016       2880

                          240     360       504          672         864

                              120      144       168         192

                                24        24          24

The equation that I will set as my conjecture will be of degree 5, in the form Sn = an5 + bn4 + cn3 + dn2 + en + f.  There are 6 unknowns, so I set up 6 equations:

U1 = a + b + c + d + e + f which equals 24 (from part a)

U2 = a25 + b24 + c23 + d22 + 2e + f

     = 32ª + 16b + 8c + 4d + 2e + f = 144

U3 = a35 + b34 + c33 + d32 + 3e + f

      = 243a + 81b + 27c + 9d + 3e + f = 504

U4 = a45 + b44 + c43 + d42 + 4e + f

      = 1024a + 256b + 64c + 16d + 4e + f = 1344

U5 = a55 + b54 + c53 + d52 + 5e + f

      = 3125a + 625b + 125c + 25d + 5e + f = 3024

U6 = a65 + b64 + c63 + d62 + 6e + f

      = 7776a + 1296b + 216c + 36d + 6e + f = 6048

These values were entered into the GDC as A  and Band it was seen by reduced row echelon form that a =, b = 2, c = 7, d = 10, e =, f = 0.

Therefore, Un = n5 + 2n4 + 7n3 +10n2 + n

Un = 1x2x3x4 + 2x3x4x5 + 3x4x5x6 + … + n(n+1)(n+2)(n+3)

     ==  

     =

Thus, = Un –

We know that = so =

Also, we know =  so =  and that

=6+12+18+…+6n can be rewritten by factoring out the 6 to make it 6(1+2+3+…+n). We    

already know 1+2+3+…+n= so, 6 times  becomes simply 3n(n+1). Finally, we  

know that Un = n5 + 2n4 + 7n3 +10n2 + n so plug these values in and:

= Un – = n5 + 2n4 + 7n3 +10n2 + n –  –    

– 3n(n+1)

=

=

Thus, my conjecture is that: =

Check:

n = 1; = 14 = 1

now try this with the above equation… = 1 [it fits!]

n = 2; = 14 + 24 = 17

now with the above equation… = 17 [it fits!]

n = 3; = 14 + 24 + 34 = 98

now with the above equation… = 98 [it fits!]

Let’s check if this conjecture works all other values of n using an induction proof:

Step 1 Assume the conjecture to be true for n = 1

As shown above,

= 14 = = 1

Step 2 Assume the conjecture to be true for n = k        

 So  =  

Step 3 Observe for if n = k + 1

= 14 + 24 + 34 + ... + k4 + (k+1)4 which, according to the formula, should equal

 =

 = + (k+1)4 = +(k+1)4                                                         =

             =  

 is equal to the equation above, so

= is true.