Sunday, September 13, 2015

elementary number theory - Prove $forall n in mathbb {N}$, $6vert (n^3-n)$. (strong induction)



Pretty straight forward idea to be proven here, but trying to grasp the fundamentals of what one would consider "strong induction". Please see my proof below, my questions are: is this a valid proof? Is this stylistically appropriate for a proof via strong induction?




EDIT: Sorry as it was not clear in my original question, but this post was more so to assist in grasping fundamentals of Strong Induction. Although thanks for pointing out the simplistic method of realizing that $(n^3-n)$ is simply the product of three consecutive integers and is thus divisible by a factor of $2$ and $3$.



Q: Prove $\forall n \in \mathbb {N}$, $6\vert (n^3-n)$.



$Proof.$ We will prove this via mathematical induction.



Base Case. Let $n=1$ and observe that $6\vert 0$ is true. Let $n=2$ and observe that $6\vert 6$ is true. Finally, let $n=3$ and observe that $6\vert 24$ is true. Thus for $n\in\mathbb{N}$ where $1\le n \le 3$ our proposition holds.



Inductive Step. Assume our proposition is true for $n=j$ where $1\le j \le k$ and $k \ge 3$. Since $6\vert (k^3-k)$ we know $k^3-k=6l$ for some $l\in\mathbb{Z}$.




Then



$$\begin{align}(k-2)^3-(k-2)&= k^3-6k^2+12k-8-k+2\\
&=(k^3-k)-6k^2+12k-6\\
&=6l-6k^2+12k-6\\
&=6(l-k^2+2k-1).
\end{align}$$



Thus $\exists m\in\mathbb{Z},(k-2)^3-(k-2)=6m\Rightarrow 6\vert (k-2)^3-(k-2)$. It follows by mathematical induction that $\forall n \in \mathbb {N}$, $6\vert (n^3-n)$. $\Box$



Answer



I'm not sure that I understand your inductive step. You say that for all $j$ such that $1\leq j\leq k, 6|j^3-j$ and $k\geq 3$. Then you should now show that this property holds for $k+1$, that is, $6|(k+1)^3+k+1$. Instead, it looks like you show me that $6|(k-2)^3-(k-2)$.



Instead, consider that $(k+1)^3-(k+1)=k^3+3k^2+2k$ and $(k-1)^3-(k-1)=k^3-3k^2+2k$. Compare the two.



Note that while this isn't the induction you're used to (sometimes called weak induction, or the first principle of induction), this "strong" induction isn't much stronger. The proof only needs the case that $k-1$ has the desired property to show that $k+1$ has the property as well. The idea of strong induction is that you would use the fact that all $j$ from $1$ to $k$ use the desired property.



A good example would be the proof of the fundamental theorem of arithmetic; to show that every number greater than $1$ has a prime factorization, we first say that $2$ is prime (the base case). Now let $k>2$, and say that for all $j$ such that $2\leq j\leq k$, $j$ has a prime factorization. If $k+1$ is prime, it is its own prime factorization. If not, it has a prime factor less than it, say $p$. Then $\frac{k+1}{p}$ has a prime factorization by the strong induction hypothesis, so $k+1$ does as well. Here, the entire assumption for all $j$ is needed, because you don't know exactly what $\frac{k+1}{p}$ is, just that it's less than $k+1$.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...