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.

For a proof by induction, you need two things. The first is a base case, which is generally the smallest value for which you expect your proposition to hold. Since you are instructed to show that the inequality holds for $n\ge3$, your base case would be $n=3$. This is usually the easy part.
The second part is your inductive step, where you assume that your proposition is true for some $n$ (and you showed in part $1$ that there is such a value) and show that it is also true for $n+1$. So here, if you know that $2n+1\le2^n$, can you show that $2(n+1)+1\le2^{n+1}$? Here, I notice that $2^{n+1}=2\cdot2^n$, so let's start by doubling the original inequality: $2(2n+1)=4n+2\le2\cdot2^n$. Also, since we know (by part of our assumption) that $n\ge3$, we know that $2n+8\le4n+2$, and $2(n+1)+1=2n+3\le2n+8$, so by transitivity we can say that $2(n+1)+1\le2^{n+1}$.
Often, figuring out how to show the $n+1$ case involves a bit of trial and error, as you try to figure out how to simplify or manipulate the equations or inequalities to get what you want. Keep in mind any restrictions on the value of $n$ that are assumed, as these may allow you to take steps that you couldn't in a more general case, as I did with $2n+8\le4n+2$, above.
