The ancient Greeks were very interested in sequences resulti

The ancient Greeks were very interested in sequences resulting from geometric shapes such as the following triangular numbers: Write a recurrence equation for the nth term in this sequence, guess a solution, and use induction to verify your solution. Into how many regions do n lines divide a plane so that every pair of lines intersect, but no more than two lines intersect at a common point? Write a recurrence equation for the number of regions for n lines, guess a solution for your equation, and use induction to verify your solution.

Solution

The recurrence relation for the sequence {1,3,6,...} will be:

S(k+1) = S(k) + (k+1) , with S(1) = 1 as initial condition

where S(k+1) denotes the (k+1)th value in the sequence

S(k) denotes the kth value of the sequence

You can try putting in some values for k = 2,3,4,.. to get the values of S(2), S(3), S(4)..., etc.

Intuitively, the solution to the above recurrence relation is k(k+1)/2. Try expanding the sequence for S(2), S(3) , S(4),... and it will be clear that S(k) = 1+2+3+....+k = k(k+1)/2.

Proof by induction :

To prove: S(k) = S(k-1) + (k) has a solution of k(k+1)/2

Base Case: S(1) = 1

S(2) = S(1) + 2 = 1 + 2 = 3

Also, k (k+1)/2 = 2(2+1)/2 = 3

Inductive Step :

Let us assume that S(k) = k(k+1)/2. With this assumption, if we can show that S(k+1) = (k+1)(k+1+1)/2, then we have proved that the real solution of the recurrence relation S(k) is k(k+1)/2.

So now let us find what is the real value of S(k+1) with the asssumption that S(k) = k(k+1)/2

S(k+1) = S(k) + (k+1), as this is the original recurrence relation

Therefore, S(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 .

Thus we see that on solving S(k+1) , we get S(k+1) = (k+1)(k+1+1)/2. Hence our assumption that S(k) = k(k+1)/2 is true, and hence the final solution for the given recurrence relation S(k) = S(k-1) + k is k(k+1)/2