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!
To prove the inductive step we have to
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.