Tips on constructing a proof by induction. So right now I'm working on a discrete mathematics course and I've been having a bit of trouble figuring out how to prove certain equations using mathematical induction. I have very little trouble understanding how to use mathematical induction to prove equations such as this: $1 + 2 ... + n = \dfrac{n(n+1)}2$ for all integers $n \ge 1$. But when it comes to less straightforward proofs such as the one I am currently working on: "Prove that $2n + 1 \le 2^n$ for $n \ge 3$" give me real trouble. Are there any tips for proofs like this any could share? Any help is greatly appreciated.

When proving inequalities by induction it’s often very helpful simply to ask yourself what happens to each side of the proposed inequality when $n$ is increased by $1$. 
In this case the expression $2n+1$ on the left increases by $2$ when you replace $n$ by $n+1$, while the expression $2^n$ on the right is multiplied by $2$ when you replace $n$ by $n+1$: instead of adding $2$, you’re adding $2^n$. If $n\ge 1$, then $2^n\ge 2$, and replacing $n$ by $n+1$ adds at least as much to the righthand side as it does to the lefthand side: it adds $2^n$ to the righthand side and $2$ to the lefthand side, and $2^n\ge 2$.
At this point you’ve already essentially done the induction step: you’ve shown that if $2n+1\le 2^n$ and $n\ge 1$, then $2(n+1)+1\le 2^{n+1}$. All that remains is to find the smallest $n\ge 1$ for which $2n+1\le 2^n$, and by actual experiment that turns out to be $n=3$.
