1
$\begingroup$

I'm a bit of a maths noob so please bear with me with what is probably a really dumb question, but I could really do with some help - I'm self-learning at home.

I'm stuck on the question below from Discrete Mathematics for Computing (Peter Grossman) on proving a recursive definition by induction. I understand everything up to the highlighted line in yellow.

It asks to create a non-recursive version of the formula

$t(n) = t(n-1) + 2n - 1$

Writing down the first few terms indicates a squares sequence, so a non-recursive form is:

$t(n) = n^2$

The question asks to then prove this is correct. The base is shown in the question, t(1) = 1 so the base is:

$t(1) = 1^2$

I then assume (inductive hypothesis) that

$t(k) = k^2$

I then need to prove that it's true for every successive term, i.e. with n = k+1. So I thought the next step would be:

$t(k+1) = (k+1)^2$

But instead the book jumps back to the original, non-recursive formula at this point (yellow line), and I just don't get that bit - surely we are now proving t(n) - t(n-1) + 2n -1 instead of t(n) = n^2? I can't assume these are equivalent at this point, as we are only conjecturing that they are the same... confused!

Thanks!

enter image description here

$\endgroup$
2
$\begingroup$

To prove the inductive step we have to

Use the assumption that $t(k) = k^2$ to prove that $t(k + 1) = (k+1)^2$.

The aim is to prove that $t(k + 1) = (k+1)^2$, but we can't just write this down; we have to derive it from the assumption that $t(k) = k^2$.

By definition, $t(n) = t(n-1) + (2n-1)$, and hence $$t(k+1) = t(k) + 2(k+1)-1$$ We then use the assumption that $t(k) = k^2$ to show that $$t(k+1) = k^2 + 2(k+1) - 1 = k^2 + 2k + 1$$

From here we can see that $$t(k+1) = (k+1)^2$$

Hence, using our assumption that the result is true for $k$, we have shown it is true for $k+1$. Since it is true for $k=1$, it is therefore true for all $k$ by induction.

$\endgroup$
2
  • $\begingroup$ Okay thanks, I think I get it now - think my confusion was not realising it's okay to assume that the first equation t(n) = t(n-1)+2n-1 IS correct and always true, and so you can use it in proving the second equation t(n) = n^2. The rest makes sense. Think I just need practice. Thank you $\endgroup$ May 12 '15 at 15:03
  • $\begingroup$ The idea is to show that given a definition of $t(n)$, there is an alternative definition given by $t(n)=n^2$, so you can certainly assume the first equation. $\endgroup$
    – Mathmo123
    May 12 '15 at 17:10
0
$\begingroup$

The point is to prove that $t(k)=k^2$ implies $t(k+1)=(k+1)^2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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