Question

A family of recurrences has the following form for constants a and c: T(1) = a T(n) = T(n-1) + c for n > 1 Solve this recurrence for T(n) in terms of a and c. Then demonstrate that you have the solution by identifying, from the list below, the correct formula for T(n) in terms of specific values of a and c. a) If a=1 and c=3, then T(n) is 3n - 2. b) If a=1 and c=3, then T(n) is n + 2. c) If a=3 and c=5, then T(n) is 3n + 2. d) If a=3 and c=5, then T(n) is 5n + 3.'

Answer 1

(a) is correct

`T(n) = a+(n-1)c`

Explanation:

Notice that according to the information that you are given

`T(1)=a \\T(2)=T(1)+c = a+c\\T(3)=T(2)+c = a+c+c = a+2c`

If you think about it there is a clear pattern, it would be

`T(n) = a+(n-1)c`

Now notice that (a) is correct if we set a=1 and c=3 we get

`T(n) = 1+3(n-1) = 3n-2`

Answer 2

T(n) = cn +(a-c)

Explanation:

Note that T(1) = a, then T(2) = a+c, T(3) = (a+c)+c = a+2c, T(4) = (a+2c)+c = a+3c. Thus, our hypotheis is that T(n) = a+(n-1)c. We will prove this by strong induction.

Note that T(1) = a = a+(1-1)c. So the base case is proved. Assume that the result is true for all k<n. Then

T(n) = T(n-1)+c = (a+(n-2)c)+c = a+(n-1)c= cn+ (a-c).

So, by induction, the result holds.

Note that if a=1 and c = 3 then T(n) = 1+(n-1)3 = 3n-3+1 = 3n-2, which invalidates option b)

If a=3 and c=5 then we have that T(n) = 5n+(3-5) = 5n-2, which invalidates c) and d).

Then the formula is correct.