1

I have no idea how to solve this. My math proving skills are pretty rusty. The problem gives the following definition to start:

$$T(n) = \begin{cases} 1 \text{ if } n = 1 \\ T(n-1) + n \text{ otherwise} \end{cases}$$

Show, by induction, that $T(n) = \frac{n(n+1)}{2}$.

My Attempt

So they're giving a recurrence relation as a place to start. So, I imagine I need to find a closed form. Expanding the piecewise function we have,

\begin{align*} T(1) &= 1 \\ T(2) &= T(2-1) + 1 \\ &= T(1) + 1 \\ &= 1 + 1 \\ &= 2 \\ T(3) &= T(3-1) + 1 \\ &= T(2) + 1 \\ &= 2 + 1 \\ &= 3 \\ &\vdots \\ T(n) &= \frac{n(n+1)}{2} \text{ since it appears to be the sum of the first n ints.} \end{align*}

Proof.

Base case. Let $n = 1$. Then, $T(1) = \frac{1(1+1)}{2} = \frac{2}{2} = 1$, as defined.

Induction. Suppose, $T(n) \implies T(n+1)$. Then by definition,

$$ \frac{n(n+1)}{2} \implies \frac{(n+1)((n+1)+1)}{2} = \frac{(n+1)(n+2)}{2} = \frac{n^2+3n+2}{2} $$

Suppose $\frac{n(n+1)}{2}$ for some $n > 1$.

This is as far as I get. I know I need to use the inductive hypothesis at some point here, I just don't know/remember how/where to do that at. Any help is greatly appreciated.

amGz
  • 7
  • 1
    You have to show that, given $T(n)=\frac{n(n+1)}{2}$ is true, that $T(n+1)=\frac{(n+1)(n+2)}{2}$ is true by the original recurrence relation. – MandelBroccoli Mar 08 '22 at 20:14
  • MandelBroccoli has given a helpful response already, but for flavor another proof is to show that this recurrence relation holds for ${n \choose 2}$ by a counting argument, after which you are done by the binomial recurrence relation. – While I Am Mar 08 '22 at 20:51
  • Question: what would the sentence " 2 implies 5" mean to you? To me, it is gibberish by someone who doesn't know what "implies" means. But this is what you've written twice. "$\implies$" means "implies". It connects two logical statements: things that can be true or false. Numbers are not statements. They cannot be true or false. $T(n), T(n+1), \frac {n(n+1)}2$ are all descriptions of numbers, not statements. – Paul Sinclair Mar 09 '22 at 15:32
  • Similarly, you cannot "Suppose $\frac{n(n+1)}2$" because "suppose" means "consider this statement to be true". But again, $\frac{n(n+1)}2$ is a number not a statement. You can no more "suppose $\frac{n(n+1)}2$" than you could "suppose George". – Paul Sinclair Mar 09 '22 at 15:45

1 Answers1

0

As I've indicated in the comments, some of your proof doesn't make any sense linquistically, and thus logically. Probably this is because induction was explained to you using a functional notation for the statements (almost certainly "$P(n)$" because for some reason "$P$" is the favored letter for this). And here you see a function $T(n)$ and are confusing it with the statement notation. But $T(n)$ is not a statement. It is just a number. The corresponding statement that is represented by $P(n)$ is "$T(n) = \frac{n(n+1)}2$".

So they're giving a recurrence relation as a place to start. So, I imagine I need to find a closed form.

No. They gave you a closed form in the problem. You don't need to find it. You just need to prove that it actually is equal to the function.

$$\begin{align*} T(2) &= T(2-1) + 1 \\ &\ \ \vdots\\ T(3) &= T(3-1) + 1\end{align*}$$

Not quite: $T(2) = T(2-1)+2, T(3) = T(3-1)+3$.

To prove a set of statements $P[n]$ for each $n \ge 1$ by (simple) induction, you prove the base case: $P[1]$, and the induction case: "$P[n] \implies P[n+1]$", or in words: for any $n$, if the statement $P[n]$ is true, then the statement $P[n+1]$ is also true.

For this problem the base case $P[1]$ is "$T(1) = \frac{1(1+1)}2$", for which your current proof is fine.

The induction case is "$P[n] \implies P[n+1]$", which is $$\left(T(n) = \frac{n(n+1)}2\right) \implies \left(T(n+1) = \frac{(n+1)(n+2)}2\right)$$ And you do not "suppose" this. This is the statement you are trying to prove. This is an implication, and the normal approach for proving an implication is to suppose that the hypothesis of the implication is true, and from that statement you then derive the conclusion.

That is, you suppose $$T(n) = \frac{n(n+1)}2$$ And then from this statement, you derive $$T(n+1) = \frac{(n+1)(n+2)}2$$ It is that derivation that proves the implication $$\left(T(n) = \frac{n(n+1)}2\right) \implies \left(T(n+1) = \frac{(n+1)(n+2)}2\right)$$

Paul Sinclair
  • 43,643
  • I see. Thank you so much for the clarification, and you are correct about my exposure to the technique using P(n). I wrote out the entire implication with the implies arrow to suggest that the part to the right of the arrow is what needs to be proven. I then "supposed" the left hand side of that implication. I guess this is where I get lost. My guess is I need to make that left hand side "look like" the right hand side, and do that by manipulation via algebra. Also, thank you for catching my mistake on interpreting the T(n) definition, I missed that it was adding n each time, not 1. – amGz Mar 09 '22 at 20:15
  • You may have meant that you were supposing just the left hand of that implication, but that is not what you actually said. Your audience doesn't get to see what is going on in your head. We can only work with what you actually say. That is why it is important to be very clear that what you say is exactly what you mean. – Paul Sinclair Mar 10 '22 at 03:12