Inductive Proofs in series

Mathematical induction about a series

Recall that statements in mathematics that seem believable but which have not yet been proven are generally known as conjectures. We can use mathematical induction to prove formulae for certain well known series.  

Let's consider a familiar example - a simple series as the sum of positive integers up to an including the integer $n$n. We will discuss this simple example by following  the typical journey that a mathematician might take whose curiosity is aroused by a imbedded pattern.   

The series of partial sums begins:  $1=1,1+2=3,1+2+3=6,1+2+3+4=10$1=1,1+2=3,1+2+3=6,1+2+3+4=10 etc. and we can label the results as $S_1=1,S_2=3,S_3=6,S_4=10,S_5=15$S1​=1,S2​=3,S3​=6,S4​=10,S5​=15 and so on.

After a time, the mathematician notices that, at least for the first few sums, the product of the last number of each partial sum and the very next integer is twice the sum itself. For example, consider the sum $S_5=1+2+3+4+5=15$S5​=1+2+3+4+5=15. The product of the last number of the sum $5$5 and the very next integer $6$6 is $30$30 which is twice the sum $S_5$S5​.  

The mathematician therefore conjectures that the sum $S_n=1+2+3+4+...+n$Sn​=1+2+3+4+...+n is given by one half of the product $n(n+1)$n(n+1). We can write formally:

$S_n=1+2+3+4+...+n=\frac{n(n+1)}{2}$Sn​=1+2+3+4+...+n=n(n+1)2​

At this point however we cannot say that this statement is generally true for any such sum up to the $n$nth integer. In fact no matter how many examples we come up with, there will always be more untested cases of the statement than tested cases. 

 

Proving the conjecture using induction

Recall that Mathematical induction involves setting up an "if-then" conditional statement.

Continuing with our example, having verified the first few cases directly, say $S_1,S_2$S1​,S2​, etc., we assume the truth of the $k$kth case $S_k$Sk​. That is to say, we assume that:

$1+2+3+...+k=\frac{k(k+1)}{2}$1+2+3+...+k=k(k+1)2​

We ask ourselves, given this assumption, does it necessarily follow that $S_{k+1}$Sk+1​ is also true. That is, we ask whether:

$1+2+3+...+k+(k+1)=\frac{[k+1][(k+1)+1]}{2}$1+2+3+...+k+(k+1)=[k+1][(k+1)+1]2​

Note that the last statement could be slightly simplified. We want to know that, given $S_k$Sk​, does it follow that:

$1+2+3+...+k+(k+1)=\frac{(k+1)(k+2)}{2}$1+2+3+...+k+(k+1)=(k+1)(k+2)2​ 

Taking the left hand side, we note that:

$1+2+3+...+k+(k+1)$1+2+3+...+k+(k+1)	$=$=	$\frac{k(k+1)}{2}+(k+1)$k(k+1)2​+(k+1)
	$=$=	$\frac{k(k+1)}{2}+\frac{2k+2}{2}$k(k+1)2​+2k+22​
	$=$=	$\frac{k^2+k+2k+2}{2}$k2+k+2k+22​
	$=$=	$$
	$=$=	$\frac{(k+1)(k+2)}{2}$(k+1)(k+2)2​
	$=$=	$RHS$RHS

We have shown that if $S_k$Sk​ is true, then it immediately follows that $S_{k+1}$Sk+1​ is also true. But, we know by direct testing that $S_1$S1​ is true. This means that $S_2$S2​ must also be true, and if $S_2$S2​ is true, then so also is $S_3$S3​, and again $S_4$S4​, and $S_5$S5​ etc. Hence it must be true for all $S_n$Sn​. 

 

More series examples

Using mathematical induction we will prove each of the listed series:

Example 2:

Prove that $a+(a+d)+(a+2d)+...+[a+(n-1)d]=\frac{n}{2}[2a+(n-1)d]$a+(a+d)+(a+2d)+...+[a+(n−1)d]=n2​[2a+(n−1)d]

This is the familiar arithmetic series sum to $n$n terms formula with first term $a$a and common difference $d$d. There are a number of ways to establish this result, but we will prove using mathematical induction.

Note first that $S_1=a$S1​=a and, using the formula, for $n=1$n=1 we have $S_1=\frac{1}{2}[2a+(1-1)d]=a$S1​=12​[2a+(1−1)d]=a so it is certainly true for $n=1$n=1.

We assume it is true for $n=k$n=k and, based on that assumption, attempt to prove the $n=k+1$n=k+1 case.

Hence we assume $S_k$Sk​ - specifically that:

$a+(a+d)+(a+2d)+...+[a+(k-1)d]=\frac{k}{2}[2a+(k-1)d]$a+(a+d)+(a+2d)+...+[a+(k−1)d]=k2​[2a+(k−1)d]

and attempt to prove $S_{k+1}$Sk+1​ - specifically to prove that:

$a+(a+d)+(a+2d)+...+[a+(k-1)d]+[a+kd]=\frac{k+1}{2}[2a+kd]$a+(a+d)+(a+2d)+...+[a+(k−1)d]+[a+kd]=k+12​[2a+kd]

Check the right hand side carefully - the $(k+1)$(k+1)th case means that the $k$k changes to $k+1$k+1 and the $k-1$k−1 changes to $k$k. 

Taking the left hand side of $S_{k+1}$Sk+1​ we have:

LHS	$=$=	$a+(a+d)+(a+2d)+...+[a+(k-1)d]+[a+kd]$a+(a+d)+(a+2d)+...+[a+(k−1)d]+[a+kd]
	$=$=	$\frac{k}{2}[2a+(k-1)d]+[a+kd]$k2​[2a+(k−1)d]+[a+kd]
	$=$=	$\frac{k}{2}[2a+(k-1)d]+\frac{2[a+kd]}{2}$k2​[2a+(k−1)d]+2[a+kd]2​
	$=$=	$\frac{2ak+k^2d+kd+2a}{2}$2ak+k2d+kd+2a2​
	$=$=	$\frac{2a(k+1)+(k+1)kd}{2}$2a(k+1)+(k+1)kd2​
	$=$=	$\frac{k+1}{2}[2a+kd]$k+12​[2a+kd]

This is precisely the right hand side we needed. Thus if it is true for $S_k$Sk​, then it is also true for $S_{k+1}$Sk+1​. we have our conditional mechanism $S_k\rightarrow S_{k+1}$Sk​→Sk+1​ and since $S_1$S1​ is true, so also is $S_2$S2​, and if $S_2$S2​ is true so also is $S_3$S3​, and so on, so that it is true for all $n$n.

 

Example 3:

Prove that the geometric series $2+6+18+...+2(3^{n-1})=3^n-1$2+6+18+...+2(3n−1)=3n−1

The partial sums $S_1=2,S_2=8,S_3=26$S1​=2,S2​=8,S3​=26 are all $1$1 less than a power of $3$3, so the result looks plausible. 

Assuming that $S_k$Sk​ is true, specifically that $2+6+18+...+2(3^{k-1})=3^k-1$2+6+18+...+2(3k−1)=3k−1, we will prove the case for $S_{k+1}$Sk+1​, namely that:

 $2+6+18+...+2(3^{k-1})+2(3^k)=3^{k+1}-1$2+6+18+...+2(3k−1)+2(3k)=3k+1−1 .

Taking the left hand side, we have;

$2+6+18+...+2(3^{k-1})+2(3^k)$2+6+18+...+2(3k−1)+2(3k)	$=$=	$3^k-1+2(3^k)$3k−1+2(3k)
	$=$=	$3^k[1+2]-1$3k[1+2]−1
	$=$=	$3\times3^k-1$3×3k−1
	$=$=	$3^{k+1}-1$3k+1−1
	$=$=	$RHS$RHS

Hence we have established $S_k\rightarrow S_{k+1}$Sk​→Sk+1​ and since $S_1$S1​ is true, then $S_2$S2​ is true, and in turn $S_3,S_4,S_5$S3​,S4​,S5​,...are true, so true for all $n$n.

 

Example 4:

Prove that $1^3+2^3+3^3+...+n^3$13+23+33+...+n3 can also be written as $(1+2+3+...+n)^2$(1+2+3+...+n)2. That is to say the sum of the first $n$n cubes is the square of the $n$nth triangular number.

This fascinating result can be written:

$1^3+2^3+3^3+...+n^3=[\frac{n(n+1)}{2}]^2$13+23+33+...+n3=[n(n+1)2​]2 

By induction then we check that $S_1$S1​ works, so that $1^3$13 should equal $[\frac{1(1+1)}{2}]^2$[1(1+1)2​]2, and it does.

We then assume the truth of the statement $S_k$Sk​:

$1^3+2^3+3^3+...+k^3=[\frac{k(k+1)}{2}]^2$13+23+33+...+k3=[k(k+1)2​]2

Finally we proceed to prove, that as a consequence of the assumption, $S_{k+1}$Sk+1​ is true. In other words we need to prove that:

$1^3+2^3+3^3+...+k^3+(k+1)^3=[\frac{(k+1)(k+2)}{2}]^2$13+23+33+...+k3+(k+1)3=[(k+1)(k+2)2​]2

Taking the left hand side, we have:

$1^3+2^3+3^3+...+k^3+(k+1)^3$13+23+33+...+k3+(k+1)3	$=$=	$[\frac{k(k+1)}{2}]^2+(k+1)^3$[k(k+1)2​]2+(k+1)3
	$=$=	$\frac{k^2(k+1)^2+4(k+1)^3}{4}$k2(k+1)2+4(k+1)34​
	$=$=	$=\frac{(k+1)^2(k^2+4k+4)}{4}$=(k+1)2(k2+4k+4)4​
	$=$=	$\frac{(k+1)^2(k+2)^2}{4}$(k+1)2(k+2)24​
	$=$=	$[\frac{(k+1)(k+2)}{2}]^2$[(k+1)(k+2)2​]2
	$=$=	RHS

This establishes $S_k\rightarrow S_{k+1}$Sk​→Sk+1​ and since $S_1$S1​ is true, so also is $S_2$S2​, and in turn $S_4$S4​, etc. hence it is true for all $n$n.

 

A further note on example 4

While the relationship has been "proven", mathematical induction can often leave us no closer to understanding why such an interesting relationship should exist in the first place.

As an example, we might look again at the last example using a different lens.  

Firstly, we can show that the difference between the squares of any two consecutive triangular numbers is a cube. For example, $10^2-6^2=64=4^3$102−62=64=43 and $15^2-10^2=125=5^3$152−102=125=53 etc . 

Since the $n$nth triangular number $T_n$Tn​ has the value $\frac{n(n+1)}{2}$n(n+1)2​ we can write that:

$T_n^2-T_{n-1}^2$T2n​−T2n−1​	$=$=	$[\frac{n(n+1)}{2}]^2-[\frac{n(n-1)}{2}]^2$[n(n+1)2​]2−[n(n−1)2​]2
	$=$=	$\frac{n^2(n+1)^2-n^2(n-1)^2}{4}$n2(n+1)2−n2(n−1)24​
	$=$=	$\frac{n^2(n^2+2n+1-n^2+2n-1)}{4}$n2(n2+2n+1−n2+2n−1)4​
	$=$=	$\frac{n^2(4n)}{4}$n2(4n)4​
	$=$=	$n^3$n3

With this established, let's now write down the pattern of differences of the squares of consecutive triangular numbers (we'll include $0^2$02 to start the pattern):

$1^2-0^2$12−02	$=$=	$1^3$13
$3^2-1^2$32−12	$=$=	$2^3$23
$6^2-3^2$62−32	$=$=	$3^3$33
$10^2-6^2$102−62	$=$=	$4^3$43
...	$=$=	...
$T_n^2-T_{n-1}^2$T2n​−T2n−1​	$=$=	$n^3$n3

Now simply add all of these results up on both sides of the equations. Immediately the relationship reveals itself. The sum of the cubes $1^3+2^3+3^3+...+n^3=T_n^2$13+23+33+...+n3=T2n​.

Does this alternative proof seem to shed more light on the deeper mathematical structure of the relationship? What do you think?