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.
 A: 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.
A: You may find the following trick to be useful. Write down a separate "reference" copy of the recurrence using a different variable:
$$T(m)=T(m-2)+7$$
Now you're going to apply this recurrence with various values plugged in for $m$, and you can record what $m$ you picked each time so you don't get confused:
$$\begin{align}
T(n)&=T(n-2)+7\,\,&[m=n]\\
  &= (T(n-2 -2)+7) +7\,\,&[m=n-2]\\
  &= T(n-4)+ 2\cdot 7\\
  &= (T(n-4-2)+7)+2\cdot 7\,\,&[m=n-4]\\
  &= T(n-6)+3\cdot7\\
  &\,\,\vdots\\
  &=T(n-2k) +k\cdot7
\end{align}$$
Taking $k=n/2+O(1)$ we get $$T(n)=O(1)+7(n/2+O(1))= \Theta(n).$$
The same trick helps with the others.
