# How does this simplification work?

The following recursive function was given:

$$T\left(n\right) = T\left(n - 1\right) + x$$

The author stated that by using repeated substitution we can solve the recurrence relation:

The basic idea is this: Given that $T\left(n\right) = T\left(n - 1\right) + x$, then we may also write $T\left(n - 1\right) = T\left(n - 2\right) + x$, provided $n>1$. Since $T(n-1)$ appears in the right-hand side of the former equation, we can substitute for it the entire right-hand side of the latter. By repeating this process we get:

\begin{align*}T\left(n\right) & = T\left(n - 1\right) + x \\ & = (T\left(n - 2\right) + x) + x \\ & = T\left(n - 2\right) + 2x \\ & = (T\left(n - 3\right) + x) + 2x \\ & = T\left(n - 3\right) + 3x \end{align*}

The next step takes a little intuition: We must try to discern the pattern which is emerging. In this case it is obvious:

$$T\left(n\right) = T\left(n - k\right) + kx$$

where $1\leq k\leq n$.

So far so good. The author then wants to show an example in which we use an inductive process:

Inductive Hypothesis: Assume that $T\left(n\right) = T\left(n - k\right) + kx$ for $k = 1, 2,..., g$. By this assumption (call this $A$):

$$T\left(n\right) = T\left(n - g\right) + gx$$

Note also that using the original recurrence relation we can write (call this $B$):

$$T\left(n - g\right) = T\left(n - g - 1\right) + x$$

for $l \leq n$. Substituting Equation $A$ in the right-hand side of Equation $B$ gives:

\begin{align*}T\left(n\right) & = T\left(n - g - 1\right) + x + gx \\ & = T\left(n - \left(g + 1\right)\right) + \left(g + 1\right)x \\ \end{align*}

This is where he lost me. How did he go from $(n - g - 1)$ to $(n - (g + 1))$?

-

He didn't go from $g-1$ to $g+1$, he went from $-g-1$ to $-(g+1)$. He simply factored out the $-1$ from both terms.

Recall that $-g$ denotes $(-1)\cdot g$, that $(-1)\cdot 1=-1$, and that $x-y$ is by definition $x+(-y)$. By making the appropriate substitutes, we get that $-g-1$ is equal to $$(-1)\cdot g +(-1)=(-1)\cdot g+(-1)\cdot 1=(-1)\cdot (g+1)$$

-
Okay, makes sense. Sorry for wasting your time lol. – David Sep 4 '14 at 0:34
Not a waste, we all have brain-farts. – Hayden Sep 4 '14 at 0:37
The author also says after the last line above "Therefore, by induction on $g$, our formula is correct for all $0\leq g\leq k$. I don't get how that's so.. – David Sep 4 '14 at 4:15
The induction process says that $T(n)=T(n-k)+kx$ holds for each $k$ such that $0\leq k \leq n$ ($n$ can be replaced if $T(0)$ is undefined, for example). Let's denote the proposition by $P_n(k)$ defined for $0\leq k \leq n$. Then it is obvious that $T(0)$ holds true, and the proof steps you give in your question show that $T(k)$ holding true implies $T(k+1)$ holding true. Then by induction, it holds for all $k$ with $0\leq k \leq n$. – Hayden Sep 4 '14 at 6:46
Did you mean $1 \leq k \leq n$? Also, I don't get how simplifying to $T(n) = T(n - (g + 1)) + (g + 1)x$ proves anything. What is that supposed to convey? – David Sep 4 '14 at 13:21

This is simply a problem of notation. He isn't saying that $g-1 = g+1$, but rather that $n-g-1 = n-(g+1)$. The key is that the minus sign after the $n$ can be distributed into the $(g+1)$. Like so: $n-g-1=n+(-1)g+(-1)1 = n+(-1)(g+1)=n-(g+1)$

-