Let n be a natural number, and let $ f:\{ i \in \mathbb{N} : 1 \le i \le n\} \rightarrow\mathbb{N} $ be a function. Show that there exists a natural number M such that $f(i) \le M $ for $1 \le i \le n $
We prove this by induction on n, when n = 1, $f(i) \le M $ for $1\le i \le1$. since if M := 1, the above holds.
now suppose that we have already proven the proposition for some $ n \ge 1$, we have to prove it for $n++$,
by the induction hypothesis, we know that there exists a natural number $ M $ such that $f(i) \le M $ for $1 \le i \le n $, in particular there must exist a natural number $ M+1$, in which case $f(i) \le M +1 $ for $1 \le i \le n++ $
Could someone shed some light on whether i have logically proved this?
Answer
You haven't proved it because neither your base-case argument nor your induction step argument is correct.
For example, when $n=1$, suppose $f$ is the function that sends $1$ to $5$. You claim that if $M=1$ then $f(i)\le M$ when $i=1$. But $f(1)=5>1=M$. What do you need to do to fix this?
As for the induction step, when $n=2$, $f$ might be the function that sends $1$ to $1$ and $2$ to $1$. So if we choose $M=1$, then $f(i)\le M$ for each $i$. But now,, if $g$ is the function that sends $1$ to $1$, $2$ to $1$ and $3$ to $5$, then it is not the case that $f(i)\le M+1$ for each $i$. Indeed $f(3)=5>2=M+1$. What do you need to do to fix this?
No comments:
Post a Comment