Another Induction Example
=========================
Prove:

  sum i = 1 to n  1/sqrt(i)  <=  2sqrt(n) - 1 for all n in N, n >= 1.

  n   sum                                   2sqrt(n) - 1

  1   1/sqrt(1) = 1                         2sqrt(1) - 1 = 1
  2   1/sqrt(1) + 1/sqrt(2)                 2sqrt(2) - 1
  3   1/sqrt(1) + 1/sqrt(2) + 1/sqrt(3)     2sqrt(3) - 1

Try to think of LS and RS inductively.
From n to n + 1:
  LS: add 1/sqrt(n+1) to previous
  RS: go from 2sqrt(n) - 1 to 2sqrt(n+1) - 1,
       same additive change as 2sqrt(n) to 2sqrt(n+1)
       = 2(sqrt(n+1) - sqrt(n))
       = 2*1/(sqrt(n+1) + sqrt(n))
Does this suggest that the result continues to be true for n+1?
Yes: (sqrt(n+1)+sqrt(n)) >= 2/(sqrt(n+1)+sqrt(n+1)) = 1/sqrt(n)

Proof
-----
For n in N, n >= 1, let P(n) be: "sum ... <= ...".

Base case, n = 1
----------------
...

Inductive Step
--------------
Let n in N, n >= 1. Suppose P(n).

Then sum i = 1 to n + 1 1/sqrt(i)
   = sum i = 1 to n 1/sqrt(i) + 1 / sqrt(n+1)  
   <= 2sqrt(n) - 1 + 1/sqrt(n+1), by IH P(n) since n >= 1.
    = 2sqrt(n) - 1 + 2/(sqrt(n+1)+sqrt(n+1))
   <= 2sqrt(n) - 1 + 2/(sqrt(n+1)+sqrt(n)), since 1/sqrt(n+1) <= 1/sqrt(n),
                                            since sqrt(n+1) >= sqrt(n).
    = 2sqrt(n) - 1 + 2(sqrt(n+1)-sqrt(n)), rationalizing the denominator
    = 2sqrt(n+1) - 1.

Care with Base Cases
====================
Define f by f(1) = 2
            f(n) = f([sqrt(n)])^2 + 3f([sqrt(n)]), n >= 2.

Here [] means floor.

Prove that f(n) is divisible by 5 for all n >= 2.

What are the base cases?