Showing $k^2-1$ is divisible by 8 when $k$ is an odd natural number Prove that $k^2-1$ is divisible by $8$ when $k$ is an odd natural number.
I am trying to prove this using induction.
Initial case: Let $k\in N$ such that $k=1$
              Then $k^2-1=1^1-1=0$.
$0\equiv 0\pmod 8$ so when $k=1$, $k^2-1$ is divisible by 8.
I am wondering how I would set up the inductive step since $k+1$ would be an even natural number. Would the inductive step in this case be showing that $((k+2)^2-1)$ is divisible by 8 instead of showing $((k+1)^2-1)$ is divisible by 8?
 A: Since $k$ is odd, therefore $k \equiv 1,3,5,7 \pmod{8}$. In which case $k^2 \equiv 1 \pmod{8}$. Thus $8$ divide $k^2-1$.
A: Let $k=2n+1$, $n$ is an integer. $k^2-1=4n^2+4n=4n(n+1)$. Either $n$ or $n+1$ is even therefore $k^2-1$ is multiple of $8$.
A: Hint:
$$ [(2k+1)^2-1] - [(2k-1)^2-1] = [4k^2+4k+1] - [4k^2-4k+1] = 8k. $$
A: The point is that we don't "use induction". Induction basically means that when we have objects in a queue with a starting object and have established a means to go from one object to the immediately adjacent object next in the queue, then we can reach any arbitrary object in the queue. This seems like common sense because it is common sense, but cannot be proven from any other assumptions that are not already as strong as it. This assumption is called the axiom of induction.
When you want to prove something about odd natural numbers, then you are asking for a queue of odd naturals. If your queue had even naturals as well, then it would be useless because if you managed to use induction you would be proving something about even naturals as well since they are in the queue. In this problem the statement is false for even naturals so you surely do not want them in your queue. What you want is all and only the odd naturals in the queue, and the means to get from one to the next in queue is by adding 2. Hence you want to prove that an odd natural has your desired property if the previous odd natural does. That is the induction step. Each step is contingent on the previous odd natural having the property. So to start the whole chain going you also want to prove that the first odd natural has that property. That is also called the base case.
