Problem with a proof by induction

Question

I'm trying to prove that $n^2+n+3$ is odd. I don't know how to figure out the solution because there isn't a formula.

Answer 1

You don't necessarily need a formula, or induction for that matter, to show $n^2+n+3$ is always odd. Consider the following: $n^2 + n = n(n+1)$.

Now: if $n$ is even, then the product of $n(n+1)$ is even, and therefore $n(n+1)+3$ is odd. Alternatively, if $n$ is odd, the $n+1$ must be even, thus the product $n(n+1)$ is even, and $n(n+1) + 3$ must be odd.

Answer 2

Proof by induction

Base case

$n=1$:
$n^2+n+3=5$, is odd, proposition true

Assumption

$n=k$:
$k^2+k+3= 2m+1$

is odd with $m$ integer.

Inductiive step

$n=k+1$:
$(k+1)^2+(k+1) + 3 =(k^2+2k+1) + (k + 1) + 3= (k^2+k+3)+ 2k+2 =\text{(by assumption)}= (2m+1) + (2(k+1)) = 2(m+k+1)+1$
which is obviously odd.

QED.

Answer 3

Sure there is a formula! To say that some number $n$ is odd is to say that $n=2m+1$ for some (whole) number $m$. And $n$ is even if and only if $n=2m$ for some number $m$.

So, to prove your proposition, we can do a proof by cases. take any number $n$. $n$ is either even or odd.

OK, assume $n$ is even. Then $n=2m$ for some $m$. So, $n^2+n+3=(2m)^2+2m+3=4m^2+2m+2+1=2(2m^2+m+1)+1$. So, there is some whole number $k$ (namely, $k=2m^2+m+1$) such that $n^2+n+3=2k+1$, and therefore $n^2+n+3$ is odd.

OK, but what if $n$ is odd? Well, then $n=2m+1$ for some $m$. Hence, $n^2+n+3=(2m+1)^2+2m+1+3=4m^2+4m+1+2m+4=2(2m^2+3m+2)+1$, and so there is some whole number $k$ (namely $k=2m^2+3m+2$) such that $n^2+n+3=2k+1$, and so once again $n^2+n+3$ is odd.

So, for any $n$, $n^2+n+3$ is odd.

P.s. I just realized that maybe by saying "there isn't a formula" you mean that "there isn't a formula that I can use where i can just plug in the givens and out comes the answer '$n^2+n+3$ is always odd". OK, if that's what you mean, then please know that mathematics is a whole lot more than just plugging things into formulas and cranking the wheel. Thank God! If that's all that mathematics would be, i would have very quickly lost interest. No, the really cool mathematics is about trying to find those patterns and accompanying formulas and theorems. What I just did abovd is called a proof, and while proofs are somewhat 'formulaic' in some of their details, for the most part it takes some creative thinking to come up with these: that's what makes math fun! So, if this is what you meant by "there isn't a formula" then quickly get it out of your head that math is just 'plug and chug' ... the plug and chug is what we learn in grade school, yes, but hopefully your teachers will move on to proofs, and leave the mindless plug and chug to calculators and computers; that's what they are good for, but we humans can do far more interesting things!