<s>[INST] Help with solving recurrence relations using iterative substitution I need help solving these two recurrences with iterative substitution. I've looked at examples, and tried to follow them, but I just don't understand the whole plugging the recurrence into itself. I tried them out, not sure if they are correct, but if someone can point me in the right direction I would be very greatful!!!
For both assume $T(n) = \theta(1)$ for $n \leq 1$.
First recurrence: 
$$
\begin{equation}
\begin{split}
T(n) &= T(n - 2) + 7 \\
& = T(n - 2 - 2) + 7 - 2 \\
&= T(n - 4) + 5 \\
&= T(n - 2^i) + 5 - 2^i \newline
&=T(n) =\theta(n)
\end{split}
\end{equation}
$$
Second recurrence:
$$
\begin{equation}
\begin{split}
T(n) &= nT(n - 1) + 1 \\
& = nT(n - 1 - 1) + 1 \\
&= n^2T(n - 2) + 1 \\
&= n^iT(n - i) + 1 \\
&= \theta(n)
\end{split}
\end{equation}
$$
I'm pretty sure the last one is wrong, I'm guessing it is $\log (n)$ from when I use the master theorem on it instead. I'm not sure though.
 [/INST] Regarding the first recurrence:

\begin{align} T(n) &= T(n - 2) + 7 \\ &= T(n - 2 - 2) + 7 - 2
 \end{align}

Should it not be
$$
T(n-2) \mapsto T(n-4)+7
$$
and
\begin{align}
T(n) &= T(n - 2) + 7 \\
&= (T((n - 2) - 2) + 7) + 7 \\
&= T(n + 2\cdot (-2)) + 2\cdot 7 \\
&= \vdots \\
&= T(n + k\cdot (-2)) + k\cdot 7
\end{align}
instead?
Regarding the second recurrence:

\begin{align} T(n) &= nT(n - 1) + 1 \\ & = nT(n - 1 - 1) + 1 
 \end{align}

This should be
$$
T(n-1) \mapsto (n-1) T(n-2) + 1
$$
and
\begin{align}
T(n) &= n T(n - 1) + 1 \\
     &= n ((n-1) T(n - 2) + 1) + 1 \\
     &= n(n-1) T(n - 2) + n + 1
\end{align}
The resulting expression might be useful, if the argument of $T$ is reduced to some known initial value.
</s>