Could you explain to me how proof by induction works?

Let's run through an example: proving by induction that n^2 = 1 + 3 + ... + (2n-1) for all integers n>0. Remember that when asked to use induction to prove a statement, you first need to show that the statement is true in what is called the 'base case', the smallest value n can take. Here the base case is n=1; substituting into the statement gives 1^2 = 1, which is true. The next step is to assume the statement is true for n=k, and from that assumption show that it is also true for n=k+1. So our assumption is: k^2 = 1 + 3 + ... + (2k-1). Our aim is to reach the same expression, but with a (k+1) in every place there is a k. So a good place to start is expanding (k+1)^2 = k^2 + 2k + 1. We can then use our assumption to substitute in the expression for k^2: (k+1)^2 = 1 + 3 + ... + (2k-1) + 2k + 1. We're almost done. We need to get a (k+1) in the final term, so try: (k+1)^2 = 1 + 3 + ... + (2k-1) + (2(k+1)-1) = 1 + 3 + ... + (2(k+1)-1) which is exactly what we wanted. So we know that if the statement is true for n=k, it's true for n=k+1. But remember we have shown that this is true for n=1. So it must be true for n=2. And then also for n=3. And so on... we say that by induction, the statement is true for all integers n>0.