1

Problem use induction to prove that $17n^3+103n$ is a multiple of 6.

Im new to learning proof by induction and was wondering if my proof would be acceptable for my maths test coming up.

Proof. base case $n=1 = 120$ $17k^3+103k=6a$ for some $a$. then we prove $k+1$ $$17(k+1)^3+103(k+1)=6b$$ for some b. we expand and get $17k^3+51k^2+51k+17+103k+103=6b$ combine like terms and substitute $17k^3+103$ for $6a$ then we get $$6a+51k^2+51k+120=6b$$ simplify to $51n(n+1)$ then we see that $n(n+1)$ has to multiply to become an even number so 51n(n+1) is also a multiple of six QED.

would this proof work or are there any better methods.

user926356
  • 1,250
allan
  • 371
  • 1
  • 10
  • 2
    You can’t just say the case with $n=k+1$ is equal to $6b$ since this assumes the statement is true and that it is indeed equal to some number divisible by 6, making the argument circular. Furthermore, you’ve dropped negatives. – KStarGamer Dec 10 '22 at 19:23
  • For the base case, you write $n=1=120$. This is not correct because $1=120$ is not correct. Also, you should say more about the number $120$. A nice way of writing it would be "If $n=1$, then $17n^3+103n=120$. And $120$ is divisible by $6$. So, the statement is true for $n=1$." – ThePortakal Dec 10 '22 at 19:57
  • You could also factor out the $6$ to show that the result for $k+1$ is a multiple of $6$: $17(k+1)^3+103(k+1)=\ldots = 6\left(a+ 17\binom{k+1}{2}+20\right),$ if binomial coefficients are allowed. – Reinhard Meier Dec 10 '22 at 20:00
  • Clearly we have $-n^3+n\equiv0\pmod6\iff-n(n-1)(n+1)\equiv0\pmod6$ because it is even and multiple of three. And by induction it is also easy. – Piquito Dec 10 '22 at 20:20

1 Answers1

1

Your base case is correct: $17(1)^3+103(1)=120$ which is divisible by $6$.

For the inductive step we assume $17k^3+103k$ is divisible by $6$ and consider $17(k+1)^3+103(k+1)$.

Expanding this we get $$17(k+1)^3+103(k+1)=17(k^3+3k^2+3k+1)+103k +103=(17k^3+103k)+51k^2+51k+120$$

We know that $17k^3+103k$ is divisible by $6$ because of the induction hypothesis. We also know that $120$ is divisible by $6$ so what we really have to show is that $51k^2+51k$ is divisible by $6$.

$51k^2+51k=51(k^2+k)$ and $51$ is divisible by $3$ so we only need to show that $k^2+k$ is even.

Now, $k$ and $k^2$ are either both even or both odd. Since the sum of two even numbers and the sum of two odd numbers are even, $k^2+k$ is even so $51k^2+51k$ is divisible by $6$.

Therefore, by induction, $17n^3+103n$ is divisible by $6$ for all $n$.

John Douma
  • 11,426
  • 2
  • 23
  • 24