How does this simplification work?

96 Views Asked by At

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))$?

2

There are 2 best solutions below

8
On BEST ANSWER

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)$$

0
On

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)$