0

I have the following statement to prove

Prove that if n is any integer then 4 either divides n^2 or n^2 − 1

I am new to proofs, how, when faced with a question like this, do I begin to decide which method of proof I should use?

Scott Adamson
  • 241
  • 1
  • 8
  • 1
    Probably easiest to consider $n$ even or odd separately – Henry Oct 04 '20 at 15:09
  • 1
    In this case, you will be successful with a proof by cases : $(1)$ $n = 2k$ $(2)$ $n=2k+1$ – Peter Oct 04 '20 at 15:09
  • 1
    To be honest I never concern myself with what type of proof to use. I first try to convince myself if it is true, then come up with a good argument. The argument will determine the type of proof. Occasionally once I have an kludgy proof I'll see a slicky more smooth method. But type of proof is much less important than having a proof. – fleablood Oct 04 '20 at 15:16
  • @Peter As a follow-up to this, for (1) if I consider n=2k, and get to n^2=4k^2, would this be correct? theres clearly some connection to 4, where would I go from there? – Scott Adamson Oct 04 '20 at 15:32
  • @ScottAdamson Correct , and in the second case $n^2-1=(2k+1)^2-1=4k^2+4k+1-1=4k^2+4k=4(k^2+k)$ – Peter Oct 04 '20 at 15:36
  • Also consider how "$a$ divides $b$" is defined : There is an integer $k$ with $ak=b$ – Peter Oct 04 '20 at 15:40

2 Answers2

1

In general it is best to prove things directly if it is possible. Think about how you can break down the possibilities for $n$, and what the implications might be for those possibilities, e.g. is $n$ even or odd?

Noah Solomon
  • 1,837
  • @ScottAdamson +1 to Noah Solomon's answer for a subtlety. In situations like this, the solver often has to choose between trying a direct proof vs proof by induction. Typically induction is often simpler, but more cumbersome. What I do, is spend 15-20 minutes first trying a direct proof, (in this case, see Peter's comment to your original query), then (if needed), 30-60 minutes trying induction. Then if problem still unsolved, I re-evaluate. – user2661923 Oct 04 '20 at 15:17
0

Try some $n$ first: $n=1$, then $n^2= 1$, or $n^2-1 =0$. So then the second option holds. $n=2$ we get $4$ and $3$ and the first option holds. For $n=3$ we get $9$ and $8$, second option. For $n=4$ we get $16, 15$ and the first. Do we see a pattern emerge?

Henno Brandsma
  • 242,131