Key Concepts and Formulas

• Recurrence Relation: A formula that defines a sequence where each term is a function of preceding terms.
• Mathematical Induction: A proof technique used to establish that a given statement is true for all natural numbers.
• One-One Function (Injective): A function where distinct elements in the domain map to distinct elements in the codomain. If $f(x_1) = f(x_2)$, then $x_1 = x_2$.
• Onto Function (Surjective): A function where every element in the codomain has at least one corresponding element in the domain.
• Composition of Functions ($f \circ g$): $(f \circ g)(x) = f(g(x))$.

Step-by-Step Solution

Step 1: Determine the explicit form of the function $f(n)$. We are given the recurrence relation $f(n + 1) = f(n) + f(1)$ for all $n \in \mathbb{N}$. The domain and codomain of $f$ are $\mathbb{N} = \{1, 2, 3, \dots\}$. Let's compute the first few terms to identify a pattern:

• For $n=1$: $f(1+1) = f(1) + f(1) \implies f(2) = 2f(1)$.
• For $n=2$: $f(2+1) = f(2) + f(1) \implies f(3) = 2f(1) + f(1) = 3f(1)$.
• For $n=3$: $f(3+1) = f(3) + f(1) \implies f(4) = 3f(1) + f(1) = 4f(1)$. The pattern suggests that $f(n) = n f(1)$.

Step 2: Prove $f(n) = n f(1)$ using mathematical induction.

• Base Case: For $n=1$, the formula states $f(1) = 1 \cdot f(1)$, which is true.
• Inductive Hypothesis: Assume that $f(k) = k f(1)$ for some $k \in \mathbb{N}$.
• Inductive Step: We need to show that $f(k+1) = (k+1)f(1)$. Using the given recurrence relation: $f(k+1) = f(k) + f(1)$ Substitute the inductive hypothesis $f(k) = k f(1)$: $f(k+1) = k f(1) + f(1)$ Factor out $f(1)$: $f(k+1) = (k+1)f(1)$ Thus, the formula holds for $k+1$. By the principle of mathematical induction, $f(n) = n f(1)$ for all $n \in \mathbb{N}$. Since $f: \mathbb{N} \to \mathbb{N}$, $f(1)$ must be a natural number, so $f(1) \ge 1$.

Step 3: Analyze Statement (B): $f$ is one-one. A function $f$ is one-one if $f(n_1) = f(n_2)$ implies $n_1 = n_2$. Let $f(n_1) = f(n_2)$ for $n_1, n_2 \in \mathbb{N}$. Using our derived formula: $n_1 f(1) = n_2 f(1)$ Since $f(1) \in \mathbb{N}$, $f(1) \ge 1$, so $f(1) \neq 0$. We can divide both sides by $f(1)$: $n_1 = n_2$ Therefore, $f$ is one-one. Statement (B) is true.

Step 4: Analyze Statement (C): If $f$ is onto, then $f(n) = n$ for all $n \in \mathbb{N}$. If $f$ is onto, then for every $m \in \mathbb{N}$ (the codomain), there exists an $n \in \mathbb{N}$ (the domain) such that $f(n) = m$. We know $f(n) = n f(1)$. So, for any $m \in \mathbb{N}$, there must exist an $n \in \mathbb{N}$ such that $n f(1) = m$. Consider $m=1$. There must exist an $n \in \mathbb{N}$ such that $n f(1) = 1$. Since $n \in \mathbb{N}$ and $f(1) \in \mathbb{N}$, both are positive integers. The only way their product can be 1 is if both are 1. So, $n=1$ and $f(1)=1$. If $f(1)=1$, then $f(n) = n \cdot 1 = n$ for all $n \in \mathbb{N}$. Therefore, if $f$ is onto, then $f(n) = n$ for all $n \in \mathbb{N}$. Statement (C) is true.

Step 5: Analyze Statement (D): If $f \circ g$ is one-one, then $g$ is one-one. Let $f \circ g$ be one-one. This means that if $(f \circ g)(x_1) = (f \circ g)(x_2)$, then $x_1 = x_2$. $(f \circ g)(x_1) = f(g(x_1))$ and $(f \circ g)(x_2) = f(g(x_2))$. So, if $f(g(x_1)) = f(g(x_2))$, then $x_1 = x_2$. We know that $f$ is one-one (from Step 3). If $f(y_1) = f(y_2)$, then $y_1 = y_2$. Let $y_1 = g(x_1)$ and $y_2 = g(x_2)$. So, if $f(g(x_1)) = f(g(x_2))$, then since $f$ is one-one, we must have $g(x_1) = g(x_2)$. This implies that if $f \circ g$ is one-one, then $g$ must be one-one. Statement (D) is true.

Step 6: Analyze Statement (A): If $g$ is onto, then $f \circ g$ is one-one. We know that $f(n) = n f(1)$ where $f(1) \in \mathbb{N}$ and $f(1) \ge 1$. Consider the case where $f(1) > 1$. For example, let $f(1) = 2$. Then $f(n) = 2n$. Let $g: \mathbb{N} \to \mathbb{N}$ be an onto function. We want to check if $f \circ g$ is one-one. This means we need to check if $f(g(n_1)) = f(g(n_2))$ implies $n_1 = n_2$. Substituting the formula for $f$: $2 g(n_1) = 2 g(n_2)$ This implies $g(n_1) = g(n_2)$. If $g$ is onto, it does not guarantee that $g$ is one-one. Let's construct a counterexample. Suppose $f(1) = 2$, so $f(n) = 2n$. Let $g: \mathbb{N} \to \mathbb{N}$ be a function such that $g(n) = 1$ for all $n \in \mathbb{N}$. This function is not onto, so this example doesn't work directly.

Let's reconsider the condition for $f \circ g$ to be one-one. We have $f(x) = c x$ where $c = f(1) \ge 1$. $(f \circ g)(n) = f(g(n)) = c \cdot g(n)$. For $f \circ g$ to be one-one, we need $c \cdot g(n_1) = c \cdot g(n_2) \implies n_1 = n_2$. If $c > 1$, we can have $g(n_1) = g(n_2)$ even if $n_1 \neq n_2$, and this would imply $f(g(n_1)) = f(g(n_2))$. For $f \circ g$ to be one-one, it must be that $g(n_1) = g(n_2) \implies n_1 = n_2$ (i.e., $g$ must be one-one), unless $c=1$.

Let's assume $g$ is onto. If $f(1) = 1$, then $f(n) = n$. In this case, $f \circ g = g$. If $g$ is onto, $f \circ g$ is onto, but not necessarily one-one. However, the statement is "If $g$ is onto, then $f \circ g$ is one-one". We are looking for a case where this is FALSE.

Consider $f(1) = 2$. So $f(n) = 2n$. Let $g: \mathbb{N} \to \mathbb{N}$ be an onto function. We need to find an onto $g$ such that $f \circ g$ is NOT one-one. Let $g(n) = 1$ if $n$ is odd, and $g(n) = k$ if $n$ is even, where $k$ is some natural number. For $g$ to be onto, the range of $g$ must be $\mathbb{N}$. So $\{1, k\} = \mathbb{N}$, which is impossible if $\mathbb{N}$ has more than 2 elements.

Let's construct a proper counterexample for statement (A). We need to show that it's possible for $g$ to be onto, but $f \circ g$ to be NOT one-one. This means there exist $n_1 \neq n_2$ such that $f(g(n_1)) = f(g(n_2))$. Since $f(x) = f(1) \cdot x$, this means $f(1) \cdot g(n_1) = f(1) \cdot g(n_2)$. If $f(1) > 1$, then this implies $g(n_1) = g(n_2)$ for $n_1 \neq n_2$. So, if $f(1) > 1$, and we can find an onto function $g$ that is NOT one-one, then statement (A) is false.

Let $f(1) = 2$, so $f(n) = 2n$. Let $g: \mathbb{N} \to \mathbb{N}$ be defined as follows: $g(n) = n$ if $n$ is odd. $g(n) = n-1$ if $n$ is even. Let's check if $g$ is onto. The range of $g$ is $\{1, 2, 3, 4, \dots\} = \mathbb{N}$. So $g$ is onto. Now let's check if $f \circ g$ is one-one. Consider $n_1 = 1$ and $n_2 = 2$. $g(1) = 1$. $f(g(1)) = f(1) = 2 \cdot 1 = 2$. $g(2) = 2-1 = 1$. $f(g(2)) = f(1) = 2 \cdot 1 = 2$. So, $f(g(1)) = f(g(2)) = 2$, but $1 \neq 2$. Therefore, $f \circ g$ is NOT one-one. This shows that if $g$ is onto, $f \circ g$ is not necessarily one-one. Statement (A) is false.

Common Mistakes & Tips

• Always verify the codomain and domain of functions. Here, $f: \mathbb{N} \to \mathbb{N}$ is crucial.
• When dealing with $f(n) = c n$, remember that $c = f(1)$ must be a natural number, so $c \ge 1$.
• For a composition $f \circ g$ to be one-one, it is a sufficient condition for $f$ and $g$ to be one-one, but not always necessary if $f$ is not the identity function. Specifically, if $f(x) = cx$ with $c>1$, then $f \circ g$ being one-one implies $g$ is one-one.

Summary

We first determined the explicit form of the function $f(n)$ as $f(n) = n f(1)$, where $f(1) \in \mathbb{N}$. We then analyzed each statement. Statement (B) was proven true as $f(n_1) = f(n_2) \implies n_1 f(1) = n_2 f(1) \implies n_1 = n_2$ since $f(1) \neq 0$. Statement (C) was shown to be true because if $f$ is onto, then $f(1)$ must be 1, leading to $f(n) = n$. Statement (D) was true because if $f \circ g$ is one-one and $f$ is one-one, then $g$ must be one-one. Statement (A) was found to be false by constructing a counterexample where $f(1) > 1$ and $g$ is an onto function that is not one-one, leading to $f \circ g$ not being one-one.

The final answer is \boxed{A}.