(a) Consider a function $f$ with $f(1)=2$ and $f(f(n))=f(n)+3 n$ for all positive integers $n$. When we substitute $n=1$, the equation $f(f(n))=f(n)+3 n$ becomes $f(f(1))=f(1)+3(1)$. Since $f(1)=2$, then $f(2)=2+3=5$. Continuing in this way, determine the value of $f(26)$.

(b) Prove that there is no function $g$ with $g(1)=2$ and $g(g(n)+m)=n+g(m)$ for all positive integers $n$ and $m$.

(c) Prove that there is exactly one function $h$ with the following properties:

- the domain of $h$ is the set of positive integers,
- $h(n)$ is a positive integer for every positive integer $n$, and
- $h(h(n)+m)=1+n+h(m)$ for all positive integers $n$ and $m$.
(a) Continuing to substitute values of $n$ back into $f(n)$, we obtain:

$$
\begin{aligned}
n=2: \quad f(f(2)) & =f(2)+3 \cdot 2 \\
f(5) & =5+6=11 \\
n=5: \quad f(f(5)) & =f(5)+3 \cdot 5 \\
f(11) & =11+15=26 \\
n=11: \quad f(f(11)) & =f(11)+3 \cdot 11 \\
f(26) & =26+33=59
\end{aligned}
$$

Therefore, $f(26)=59$.

(b) We show that there is no such function $g$ by using the given information to derive two different outputs for a single input, which will give a contradiction of the important property of a function that there is only one output for a given input.

At each step, we use values of $m$ and $n$ for which we already know the values of $g(m)$ and $g(n)$, which limits our options at each step.

Assume that there exists a function $g$ with $g(1)=2$ and $g(g(n)+m)=n+g(m)$.

- If $n=1$ and $m=1$, then $g(g(1)+1)=1+g(1)$ or $g(2+1)=1+2$ and so $g(3)=3$.
- If $n=1$ and $m=3$, then $g(g(1)+3)=1+g(3)$ or $g(2+3)=1+3$ and so $g(5)=4$.
- If $n=3$ and $m=1$, then $g(g(3)+1)=3+g(1)$ or $g(3+1)=3+2$ and so $g(4)=5$.
- If $n=3$ and $m=2$, then $g(g(3)+2)=3+g(2)$ or $g(3+2)=3+g(2)$.

Since $g(5)=4$, then $4=3+g(2)$ or $g(2)=1$.

- If $n=2$ and $m=4$, then $g(g(2)+4)=2+g(4)$ or $g(1+4)=2+5$ and so $g(5)=7$.

Since $g(5)=4$ and $g(5)=7$, we have a contradiction.

Therefore, there does not exist such a function $g$.

## (c) Solution 1

First, we show that the function $h(n)=n+1$ for each positive integer $n$ satisfies the conditions.

We note that this function satisfies the first two conditions.

Thus, if $h(n)=n+1$ for each positive integer $n$,

$$
h(h(n)+m)=h(n+1+m)=(n+1+m)+1=n+m+2
$$

and

$$
1+n+h(m)=1+n+m+1=n+m+2
$$

and so the third condition is satisfied.

Next, we show that there is no other such function.

Suppose that the function $h$ satisfies the three conditions and that $h(1)=k$.

Step 1: Show that $h(a+r k)=h(a)+2 r$ for each integer $r \geq 1$

Using the functional equation with $n=1$ and $m=a$, we obtain $h(h(1)+a)=1+1+h(a)$ or $h(a+k)=h(a)+2$.

Using the functional equation with $n=1$ and $m=a+k$, we obtain

$$
h(h(1)+a+k)=1+1+h(a+k)
$$

or $h(a+2 k)=2+h(a)+2=h(a)+4$.

Using the functional equation with $n=1$ and $m=a+2 k$, we obtain

$$
h(h(1)+a+2 k)=1+1+h(a+2 k)
$$

or $h(a+3 k)=2+h(a)+4=h(a)+6$.

Assume that $h(a+(r-1) k)=h(a)+2(r-1)$ for some integer $r \geq 2$.

Using the functional equation with $n=1$ and $m=a+(r-1) k$, we obtain

$$
h(h(1)+a+(r-1) k)=1+1+h(a+(r-1) k)
$$

or $h(a+r k)=2+h(a)+2(r-1)=h(a)+2 r$.

Step 2: Show that if $h(b)=h(c)$, then $b=c$

In other words, we show that the function $h$ is one-to-one.

Suppose that $h(b)=h(c)$.

Then for each positive integer $d, h(h(b)+d)=1+b+h(d)$ and $h(h(c)+d)=1+c+h(d)$. Since $h(b)=h(c)$, then $h(h(b)+d)=h(h(c)+d)$ and so $1+b+h(d)=1+c+h(d)$ or $b=c$.

Step 3: Show that $k \leq 2$

From Step 1, $h(a+r k)=h(a)+2 r$ for all positive integers $a$ and $r$.

Suppose that $k \geq 3$.

When $a=1$, we obtain $h(1+r k)=h(1)+2 r$ for each positive integer $r$.

The values of $h$ here form an infinite set of positive integers starting with $h(1)+2$ which are spaced 2 apart.

When $a=2$, we obtain $h(2+r k)=h(2)+2 r$ for each positive integer $r$.

The values of $h$ here form an infinite set of positive integers starting with $h(2)+2$ which are spaced 2 apart.

When $a=3$, we obtain $h(3+r k)=h(3)+2 r$ for each positive integer $r$.

The values of $h$ here form an infinite set of positive integers starting with $h(3)+2$ which are spaced 2 apart.

Since $k \geq 3$, then the inputs in these three sets are all distinct, since those in the first family give remainder 1 when divided by $k$, those in the second family give remainder 2 when divided by $k$, and those in the third family give remainder 3 (or possibly 0 if $k=3$ ). But the three sets of outputs $h(1)+2 r, h(2)+2 r, h(3)+2 r$ must overlap eventually, as there can be only two disjoint infinite sets with common difference 2 .

This is a contradiction, so we cannot have $k \geq 3$, which means that $k \leq 2$.

Step 4: Show that $k=2$

We know that $k=1$ or $k=2$.

If $h(1)=k=1$, the equation $h(1+r k)=h(1)+2 r$ becomes $h(1+r)=1+2 r$.

Substituting $n=1+r$ (or $r=n-1$ ) gives $h(n)=1+2(n-1)=2 n-1$.

In this case,

$$
h(h(n)+m)=h(2 n-1+m)=2(2 n-1+m)-1=4 n+2 m-3
$$

and

$$
1+n+h(m)=1+n+2 m-1=n+2 m
$$

These two expressions are not always equal for all $n$ and $m$ (for example, when $n=m=2$ ). Therefore, we cannot have $k=1$. Thus, $k=2$.

Step 5: $h(n)=n+1$ when $n$ is odd

From $h(1+r k)=h(1)+2 r$ and $k=2$, we obtain $h(1+2 r)=2+2 r=(2 r+1)+1$ and so $h(n)=n+1$ when $n$ is odd.

Step 6: $h(n)=n+1$ when $n$ is even

From $h(2+r k)=h(2)+2 r$, we obtain $h(2+2 r)=h(2)+2 r$.

If we can show that $h(2)=3$, then we will obtain $h(2+2 r)=3+2 r$ as required.

Since $h(x)$ is even when $x$ is odd and since $h$ is one-to-one, then $h(x)$ must be odd when $x$ is even.

In particular, $h(2)$ is odd.

From $h(h(n)+m)=1+n+h(m)$ with $n=2$ and $m=1$, we get $h(h(2)+1)=1+2+h(1)$ and so $h(h(2)+1)=5$.

When $n$ is even, the values of $h(n)$ form an increasing sequence of odd positive integers.

This is because $h(2)$ is odd and so $h(2)+2 r$ is odd and increasing as $r$ increases, and so $h(2+2 r)=h(2)+2 r$ is odd and increasing as $r$ increases.

Therefore, $h(h(2)+1)=5$ has to be the third smallest, or second smallest, or smallest value of $h(n)$ when $n$ is even.

Since $h(2+2 r)=h(2)+2 r$, then the values of $h(x)$ when $x$ is even increase when $x$ increases by 2 .

This means that we must have $h(6)=5$ or $h(4)=5$ or $h(2)=5$.

If $h(6)=5$, then $h(h(2)+1)=5$ gives $h(2)+1=6$ or $h(2)=5$, which cannot be the case, since $h$ is one-to-one.

If $h(2)=5$, then $h(h(2)+1)=5$ gives $h(2)+1=h(2)$ which cannot be the case.

Therefore, $h(4)=5$ and so $h(2+2)=h(2)+2$ which gives $h(2)=5-2=3$.

We have shown that the function $h(n)=n+1$ satisfies the given condition and that no other function does, as required.

Solution 2

Let $h$ be a function that satisfies the given properties, and consider the infinite set of lattice points of the form $(m, h(m))$, for $m=1,2,3, \ldots$.

Let $a$ be a positive integer.

When $n=a$ and $m=h(a)$, the functional equation is $h(h(a)+h(a))=1+a+h(h(a))$ or $h(2 h(a))=1+a+h(h(a))$.

Thus, the point $(2 h(a), 1+a+h(h(a)))$ is on the graph of $y=h(x)$.

When $n=a$ and $m=2 h(a)$, the functional equation becomes

$$
h(h(a)+2 h(a))=1+a+h(2 h(a))
$$

or $h(3 h(a))=1+a+1+a+h(h(a))=2+2 a+h(h(a))$.

Thus, the point $(3 h(a), 2+2 a+h(h(a)))$ is on the graph of $y=h(x)$.

Suppose that $r$ is a positive integer and assume that $h(r h(a))=(r-1)+(r-1) a+h(h(a))$. When $n=a$ and $m=r h(a)$, the functional equation becomes

$h(h(a)+r h(a))=1+a+h(r h(a))=1+a+(r-1)+(r-1) a+h(h(a))=r+r a+h(h(a))$

or $h((r+1) h(a))=r+r a+h(h(a))$.

Thus, if the point $(r h(a),(r-1)+(r-1) a+h(h(a)))$ is on the graph of $y=h(x)$, then the point $((r+1) h(a), r+r a+h(h(a)))$ is on the graph of $y=h(x)$.

This shows that the infinite set of points of the form $(\operatorname{sh}(a),(s-1)+(s-1) a+h(h(a)))$ for integers $s \geq 2$ all lie on this graph.

Note that to get from one point in this set to the next, we move $h(a)$ units to the right and $a+1$ units up.

In other words, this infinite set of points on the graph forms a line with slope $\frac{a+1}{h(a)}$.

Call this line $L_{a}$.

Suppose that $b$ is a positive integer with $b \neq a$.

A similar argument shows that the set of points $(t h(b),(t-1)+(t-1) b+h(h(b)))$ for integers $t \geq 2$ all lie on this graph, which thus form a line $L_{b}$ with slope $\frac{b+1}{h(b)}$.

Now consider the points $(n, h(n))$ on the graph of $y=h(x)$ where $n$ is a positive integer that is a multiple of $h(a)$ and is also a multiple of $h(b)$.

There are infinitely many such points (for example, $n=w h(a) h(b)$ for positive integers $w$ ). These points lie on both $L_{a}$ and $L_{b}$, and so the slopes of these two lines must be equal. But this is true for every possible pair of distinct positive integers $a$ and $b$.

Therefore, the quantity $\frac{a+1}{h(a)}$ must be constant for all positive integers $a$. (Another way to see this is to let $a=1$ and let $b$ range through all positive integers greater than 1.)

In other words, $\frac{a+1}{h(a)}=\frac{1}{c}$ for some constant $c$ or $h(a)=c a+c$ for all positive integers $a$. If $a=1$, then $h(1)=c+c=2 c$.

Setting $n=m=1$ in the equation $h(h(n)+m)=1+n+h(m)$, we obtain $h(h(1)+1)=1+1+h(1)$ which gives $h(2 c+1)=2+2 c$.

Since $h(a)=c a+c$, then setting $a=2 c+1$ gives $c(2 c+1)+c=2+2 c$ or $2 c^{2}+2 c=2+2 c$ and so $c^{2}=1$.

Since $c>0$, then $c=1$ and so $h(n)=n+1$.

(Solution 1 shows us that the function $h(n)=n+1$ does satisfy the requirements.)