Guided solutions for Elementary Number Theory 21 Problem 2 P

Guided solutions for Elementary Number Theory 2.1 Problem 2 P Question If tn denotes the nth triangular number, prove that in terms of the binomial coefficients. tn = (n +1/2) n greater than or equal to 1

Solution

The triangular number series is :

1 , 3 , 6 , 10 , 15 , 21 , 28 , .....

To prove : Tn = (n + 1) C (2)

Step 1 : Let us first prove that it is true for n = 1

T1 = (1 + 1) C 2
1 = 2C2(From the list above, T1, first term = 1)
1 = 1
So, satisfies

Step 2 : Assume it is true for n = k

Tk = (k + 1) C 2

Step 3 : W emust prove that it is true for n = k + 1

T(k+1) = (k + 2) C 2

Subtract Tk both sides :

T(k+1) - T(k) = (k + 2) C 2 - (k + 1) C 2

Now, the difference between the (k+1)th and (k)th terms is : k + 1

So, k + 1 = (k + 2) C 2 - (k + 1) C 2

Taking the right :

(k+2)C2 = (k+2)! / (2! * k!) --> (k+2)(k+1)k! / (2*k!) --> (k+2)(k+1)/2
(k + 1)C2 = (k+1)! / (2! * (k-1)!) --> (k+1)(k)(k-1)! / 2(k-1)! --> (k+1)(k)/2

So, (k+2)(k+1)/2 - k(k+1)/2

(k^2 + 3k + 2)/2 - (k^2 + k)/2

(k^2 + 3k + 2- k^2 - k) / 2

(2k + 2) / 2

k + 1

Hence left = right

So, proved for n = k + 1

And hence, by the principles of math induction, it has been proved