Define the function fN rightarrow N with fnn2 n 1 Use the

Define the function f:N rightarrow N, with f(n)=n^2 + n + 1. Use the following two different methods to prove that f is injective. By contradiction. Suppose it is not injective and find a contradiction. I would suggest a good first line is \"Assume that n notequalto m, n, m elementof N, and f(m). We not that it is OK to assume, without loss of generality, that m

Solution

Consider any two numbers m <n.

If possible let f(m) = f(n)

Then m²+m+1 = n²+n+1

Cancel 1 and simplify to have

(m+n)(m-n) +(m-n) =0

or (m-n)(m+n+1) =0

m+n+1 cannot be 0 as m,n are natural numbers

Hence only possibility m=n.

f is injective.

--------------------------------------

Method II:

f(n) = n^2+n+1

f\'(n) = 2n+1 >0 for n >0

Hence f is monotonically increasing

For m>n, f(m) >f(n)

So f is oneto one or injective.