Basic Recurrence Relation Problem

A factory makes custom sports cars at an increasing rate. In the first month only one car

is made, in the second month two cars are made, and so on, with n cars made in the nth

month.

(a) Set up a recurrence relation for the number of cars produced in the first n months by

this factory.

(b) How many cars are produced in the first year?

a. I think this would be a_{n = }a_{n-1} + 1, but something tells me it might be a_{n = }a_{n-1} + n, I am not sure.

b. Would this just be 1+2+3+4+5+6+7+8+9+10+11+12? Or, plugging in 12 for the above equation?

Thanks.

Re: Basic Recurrence Relation Problem

Hi Walshy,

Let's make a little diagram that we can check all of our answers with.

Month | Cars Made This month | Cares Made to Date |

1 | 1 | 1 |

2 | 2 | 3 |

3 | 3 | 6 |

4 | 4 | 10 |

5 | 5 | 15 |

... | ... | ... |

n | a_{n} | S_{n} |

A. Following the pattern, S_{n} = S_{n-1}+a_{n}. Yet, a_{n} = n, so we have that the number of cars made to date in the nth month is S_{n} = S_{n-1}+n. But S_{n-1} = S_{n-2} + n-1, so S_{n} = S_{n-2} +(n-1) + n. Thus, continuing its recursive definition, S_{n} = S_{n-3} + (n-2) + (n-1) + n. Continuing this until we get down to the first month, this is S_{n} = 1 + 2 + ... + n, which can be shown to equal (by the sum of an arithmetic sequence):

S_{n} = $\displaystyle \frac{n(n+1)}{2}$

With a quick check of out table, we can see that this gives us the third entry in every row.

$\displaystyle \frac{1*2}{2} = 1$

$\displaystyle \frac{2*3}{2} = 3$

$\displaystyle \frac{3*4}{2} = 6$

...

B. After the first year (n = 12), we can either substitute n=12 into the formula above or do 1 + 2 + ... + 12. Either way, we get 78 cars produced.