I find inductive proofs tend to leave me hanging - I become convinced that the conclusion is true, but I still have no intuition as to why. For example, Wikipedia's proof [0] that sum of 0..n == n(n+1)/2 is convincing, but unenlightening. There are proofs which seem much more "elegant" to me, for example, pairing (1+n) == (2+n-1) == (3+n-2) ... (n/2 + (n/2 + 1)) [1], or constructing triangles [also 1].
The book I mentioned above, Concrete Mathematics, talks about how to develop an intuition when it comes to induction. One of the advice mentioned is to always start with smallest cases possible because that makes the problem easier to understand. I suppose the more you practice the better your intuition becomes.
[0] http://en.wikipedia.org/wiki/Mathematical_induction#Example
[1] http://betterexplained.com/articles/techniques-for-adding-th...