Solution to recurrence relation $T(n)=T(n-1)+2$ is given by, where $n=0$ and $T(0)=5$

Question

Solution to recurrence relation $T(n)=T(n-1)+2$ is given by, where $n>=0$ and $T(0)=5$

Accepted Answer

The correct option is (3):
The recurrence relation $T(n)=T(n-1)+2$ is a simple first-order linear recurrence relation that represents an arithmetic progression, where the term for $n$ is always 2 greater than the term for $n-1$. To solve this and find a closed-form expression, we use the method of iteration (or unrolling). Starting with $T(n)$, we substitute the relation repeatedly: $T(n) = T(n-1) + 2 = (T(n-2) + 2) + 2 = T(n-2) + 2 \times 2$. Continuing this for $n$ steps, we reach the expression $T(n) = T(n-n) + n \times 2$, which simplifies to $T(n) = T(0) + 2n$. Substituting the initial condition, $T(0)=5$, into this general solution gives the final correct closed-form solution: $T(n) = 5 + 2n$, or $T(n) = 2n + 5$.

The incorrect option is (1):
The proposed solution is $T(n)=2n-5$. This option fails the crucial initial condition check. If we substitute $n=0$ into this formula, we get $T(0) = 2(0) - 5 = -5$. This contradicts the given base case, which explicitly states that $T(0)=5$. Since the closed-form solution must hold true for the base case, this option is immediately ruled out. The formula's constant term should be $+5$, reflecting the starting value, not $-5$.

The incorrect option is (2):
The proposed solution is $T(n)=n-5$. Similar to the previous option, testing this with the base case $n=0$ yields $T(0) = 0 - 5 = -5$, which contradicts the required initial condition of $T(0)=5$. Furthermore, for $n=1$, this formula gives $T(1) = 1-5 = -4$, whereas the correct recurrence relation must yield $T(1) = T(0) + 2 = 5 + 2 = 7$. The coefficient of $n$ in the correct solution is 2, indicating the constant addition in the recurrence, but here it is incorrectly 1.

The incorrect option is (4):
The proposed solution is $T(n)=n-3$. This option also fails the base case test, as substituting $n=0$ results in $T(0) = 0 - 3 = -3$, which is not the required $T(0)=5$. Even if the initial condition were correct, this formula would generate a difference of 1 between consecutive terms, as $T(n) - T(n-1) = (n-3) - ((n-1)-3) = n-3 - n + 1 + 3 = 1$. This is incorrect because the recurrence relation $T(n)=T(n-1)+2$ mandates a difference of 2 between consecutive terms.