Tuesday, November 28, 2017

induction - Every natural number n greater than or equal to 6 can be written in the form n = 3k +4t for some k,t in N



Prove by strong induction that every natural number $n \geq6$ can be written in the form $n=3k+4t$ for some $k,t \in \mathbb{N}$.




I'm not entirely comfortable with the concept of strong induction. I believe you assume that $P(1), P(2), P(3),... P(n)$ are true to prove $P(n+1)$ is. Now, how does that fit into this problem? Would the base case be where $n=6$?


Answer



$P(1)$ through $P(5)$ are vacuously true because $1$ through $5$ are not greater than or equal to $6$. Your base cases are $6,7,8$. Show by example that you can do each of them. Intuitively, you can just add enough $3$s to get to any number. So assume it is true up to $n$, then to do $n+1$ you say that you can do $n-2$ and add a $3$


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...