Check that this pattern is consistent with your substitutions, but you do not need to formally prove it is correct via induction. i) T(n) = T(n - 1) + 1 ii) T(n) = T(n - 3) + 4

Given:

Assume that, $T\left(1\right)=1$.

(i)

Assume that the recurrence relation is$T\left(n\right)=T\left(n-1\right)+1$.

Obtain the recurrence relation such that the terms are look like after the k^th substitution.

Substitute $n=n-1$ in the recurrence relation.

$\begin{array}{rcl}T\left(n-1\right)& =& T\left(n-1-1\right)+1\\ & =& T\left(n-2\right)+1\end{array}$

Substitute $n=n-2$ in the recurrence relation.

$\begin{array}{rcl}T\left(n-2\right)& =& T\left(n-2-1\right)+1\\ & =& T\left(n-3\right)+1\end{array}$

Therefore, $T\left(n\right)=T\left(n-3\right)+3$.

By the above recurrence relation, $T\left(n\right)=T\left(n-4\right)+4$.

In general, after the k^th substitution the recurrence relation $T\left(n\right)=T\left(n-k\right)+k$.

Let's prove the recurrence relation by induction on k.

when $k=1$, $T\left(n\right)=T\left(n-1\right)+1$.

Assume that, the recurrence relation is true for $k=k-1$.

 $\begin{array}{rcl}T\left(n\right)& =& T\left(n-\left(k-1\right)\right)+k-1\\ & =& T\left(n-k+1\right)+k-1\end{array}$

Since $\begin{array}{rcl}T\left(n-k+1\right)& =& T\left(n-k\right)+1\end{array}$, the recurrence relation $\begin{array}{rcl}T\left(n\right)& =& T\left(n-k+1\right)+k-1\end{array}$ becomes,

$\begin{array}{rcl}T\left(n\right)& =& T\left(n-k\right)+1+k-1\\ & =& T\left(n-k\right)+k\end{array}$

Therefore, the recurrence relation after the k^th substitution is $T\left(n\right)=T\left(n-k\right)+k$.

(ii)

Assume that the recurrence relation is$T\left(n\right)=T\left(n-3\right)+4$.

Obtain the recurrence relation such that the terms are look like after the k^th substitution.

Substitute $n=n-3$ in the recurrence relation.

$\begin{array}{rcl}T\left(n-3\right)& =& T\left(n-3-3\right)+4\\ & =& T\left(n-6\right)+4\end{array}$

Substitute $n=n-6$ in the recurrence relation.

$\begin{array}{rcl}T\left(n-6\right)& =& T\left(n-6-3\right)+4\\ & =& T\left(n-9\right)+4\end{array}$

Therefore, $T\left(n\right)=T\left(n-9\right)+12$.

By the above recurrence relation, $T\left(n\right)=T\left(n-12\right)+16$.

In general, after the k^th substitution the recurrence relation $T\left(n\right)=T\left(n-3k\right)+4k$.

Let's prove the recurrence relation by induction on k.

when $k=1$, $T\left(n\right)=T\left(n-3\right)+4$.

Assume that, the recurrence relation is true for $k=k-1$.

 $\begin{array}{rcl}T\left(n\right)& =& T\left(n-3\left(k-1\right)\right)+4\left(k-1\right)\\ & =& T\left(n-3k+3\right)+4k-4\end{array}$

Since $\begin{array}{rcl}T\left(n-3k+3\right)& =& T\left(n-3k\right)+4\end{array}$, the recurrence relation $\begin{array}{rcl}& & T\end{array}\begin{array}{rcl}& & \left(n\right)\end{array}\begin{array}{rcl}& =& \end{array}\begin{array}{rcl}& & T\end{array}\begin{array}{rcl}& & \left(n-3k+3\right)\end{array}\begin{array}{rcl}& & +\end{array}\begin{array}{rcl}& & 4\end{array}\begin{array}{rcl}& & k\end{array}\begin{array}{rcl}& & -\end{array}\begin{array}{rcl}& & 4\end{array}$ becomes,

$\begin{array}{rcl}T\left(n\right)& =& T\left(n-3k+3\right)+4k-4\\ & =& T\left(n-3k\right)+4+4k-4\\ & =& T\left(n-3k\right)+4k\end{array}$

Therefore, the recurrence relation after the k^th substitution is $T\left(n\right)=T\left(n-3k\right)+4k$.