Resolve recursive dependences using substitution method

Question

Resolve recursive dependences using substitution method and prove it with mathematical induction:

1.T(1) = 1
T(n) = T(n – 1) + n for n > 1

2. T(1) = 0
T(n) = T(n/2) + 1 for even numbers n > 1
T(n) = T((n + 1)/2) + 1 for odd numbers n > 1

In the second point, it's enough that you'll get the solution for n=2^k and natural number k.

I don't understand the substitution method yet.

In the first point, I've got:

T(n) = n(n-1) + 1

But this doesn't seem to be right because proof says it's wrong. And what does it mean that: it's enough that you'll get the solution for n=2^k and natural number k.

Answer 1

Let's rewrite the first as T(n + 1) = T(n) + n + 1.
Then T(1) = 1, T(2) = 1 + 2, T(3) = do you see the pattern?