Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
Okay, makes sense. Sorry for wasting your time lol. –  David Sep 4 at 0:34
    
Not a waste, we all have brain-farts. –  Hayden Sep 4 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 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 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 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)$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.