Chapter 9

Solve \(T(n)=T(n-1)+n\) for \(n \geq 2\) with \(T(1)=1\).

Solve \(T(n)=T(n-1)+n\) for \(n \geq 2\) with \(T(1)=0 .\)

Let \(f(n)\) be the number of strings of \(n\) symbols formed using the symbols \(0,1,\) and 2 such that no two consecutive \(0^{\circ}\) s occur. Show that \(f(n)=2 f(n-1)+2 f(n-2)\) Solve the recurrence, and enumerate all such strings of length four.

Solve \(T(n)=T(n-1)+n^{3}\) for \(n \geq 1\) with \(T(0)=0\).

Solve \(T(n)=T(n-1)-n+3\) for \(n \geq 1\) with \(T(0)=2\).

Solve \(T(n)=T(n-1)+2\) for \(n \geq 1\) with \(T(0)=1\).

Consider \(n\) coplanar straight lines, no two of which are parallel and no three of which pass through a common point. Find and solve the recurrence relation that describes the number of disjoint areas into which the lines divide the plane.

Find and solve the recurrence relation that describes the number of regions created by mutually overlapping circles on a piece of paper provided no three circles have a common intersection point and each pair of circles intersects in exactly two points. Begin by drawing a picture for such a configuration when \(n=1,2,3,\) and \(4 .\)

A very old puzzle book (dated 1917 ) contained the following problem: A man had a basket containing \(n\) potatoes. He asked his child to place these potatoes on the ground in a straight line. The distance between the first and second potatoes was to be one yard, between the second and third potatoes three yards, between the third and fourth potatoes five yards, and so on. After placing all the potatoes as required, how far would the child walk, starting at the first potato, to pick up all \(n\) potatoes? How many potatoes would the child pick up in the first mile of walking?

The population of a fruit fly colony doubles every day. If a colony of fruit flies has 100 members at the start of an experiment, how many fruit flies will be present after \(n\) days? If the population triples every day, how many fruit flies will be present after \(n\) days?