contestada

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.'

Respuesta :

Answer:

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

Step-by-step 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.

Answer:

(a) is correct

[tex]T(n) = a+(n-1)c[/tex]

Step-by-step explanation:

Notice that according to the information that you are given

[tex]T(1)=a \\T(2)=T(1)+c = a+c\\T(3)=T(2)+c = a+c+c = a+2c[/tex]

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

[tex]T(n) = a+(n-1)c[/tex]

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

[tex]T(n) = 1+3(n-1) = 3n-2[/tex]

Otras preguntas