See the thread Adam started for a hint on Theorem 1.
Theorem 2 requires two halfs. For each half, you can do whatever proof technique (direct, contradiction, or contrapositive) makes sense to you. You can do each half differently. This one is probably the hardest of the four theorems (in my opinion) despite looking easy on the surface.
Try weak induction for Theorem 3. This problem is one of my favorites. To get some intution, take the picture that I drew for 5 points and ask yourself how many additional lines you would need to add if you added a 6th point. And then how many new lines if you added a 7th? How many new lines would you need to add to a circle with $k$ points and all the lines if you added one more point? Once you set this one up correctly, it is very short.
For Theorem 4, use strong induction and mimick the proofs we've done involving the Fibonacci sequence (except this isn't the Fibonacci sequence). If you know how to phrase the first sentence of the inductive step correctly, there aren't really any tricks. Don't get bogged down in the indices. The recurrence relation says: each term is equal to 5 times the previous term minus 6 times the terms before that. For example, $a_{11}=5a_{10}-6a_{9}$. Despite appearances, this one is quite friendly.
