# Basic Recurrence Relation Problem

Printable View

• November 29th 2012, 04:53 PM
Walshy
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 an = an-1 + 1, but something tells me it might be an = an-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.
• November 29th 2012, 05:24 PM
Stephen347
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     | an                   | Sn                 |

A. Following the pattern, Sn = Sn-1+an. Yet, an = n, so we have that the number of cars made to date in the nth month is Sn = Sn-1+n. But Sn-1 = Sn-2 + n-1, so Sn = Sn-2 +(n-1) + n. Thus, continuing its recursive definition, Sn = Sn-3 + (n-2) + (n-1) + n. Continuing this until we get down to the first month, this is Sn = 1 + 2 + ... + n, which can be shown to equal (by the sum of an arithmetic sequence):
Sn = $\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.
$\frac{1*2}{2} = 1$
$\frac{2*3}{2} = 3$
$\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.
All times are GMT -8. The time now is 09:00 AM.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 4, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8832105994224548, "perplexity_flag": "middle"}