Solution First notice that ("first property") \[f(n+1) = \frac{(f(n)+n-k)^{2}}{f(n)};\\ f(n+1) = \frac{(f(n))^{2}+2(n-k)f(n)+(n-k)^{2}}{f(n)},\] and because $f(n+1)$ is an integer, $f(n)$ divides $(n-k)^{2}$ if $n \neq k$ and $n \leq 2$. Let $n_{p}$ be an integer smaller or equal to $-2$, such that $(k-n_{p})$ is a prime greater or equal to $7$. Notice that $f(n_{p})$ divides $(k-n_{p})^{2}$. Let $p$ now be a prime (greater or equal to 7), such that $k-n_{p}= p$, so $f(n_{p})$ divides $p^{2}$. Now notice that \[f(n_{p}-1)f(n_{p})=(f(n_{p}-1)+n_{p}-1-k)^{2}\Leftrightarrow (f(n_{p}-1))^{2}+2(n_{p}-1-k)f(n_{p}-1)+(n_{p}-1-k)^{2}-f(n_{p})f(n_{p}-1)=0;\\ f(n_{p}-1)f(n_{p})=(f(n_{p}-1)+n_{p}-1-k)^{2}\Leftrightarrow (f(n_{p}-1))^{2}+(-2p-f(n)-2)f(n_{p}-1)+(-p-1)^{2}=0;\\ f(n_{p}-1)f(n_{p})=(f(n_{p}-1)+n_{p}-1-k)^{2}\Leftrightarrow (f(n_{p}-1))^{2}+(-2p-f(n)-2)f(n_{p}-1)+(p+1)^{2}=0.\] Now we'll calculate the discriminant of this equation with variable $f(n_{p}-1)$ ("second property"): \[D = (-2p-f(n)-2)^{2}-4 \cdot 1 \cdot (p+1)^{2};\\ D = (f(n)+2p+2)^{2}-4 (p+1)^{2}.\] Because $f(n_{p})$ is a divisor of $p^{2}$, $f(n_{p})$ can only be equal to $-p^{2},-p,-1, 1, p, p^{2}$. By plugging $f(n_{p}) = p^{2}$ into the first property, we get $f(n_{p}+1)=(p-1)^{2}$, and by plugging $f(n_{p}) = 1$ into the first property, we get $f(n_{p}+1)=(p-1)^{2}$. Now if we assume $f(n_{p})=p$, our second property yields \[D = (3p+2)^{2}-4(p+1)^{2};\\ D = p(5p+4).\] Now notice that $D$ needs to be a perfect square and that $p$ divides $D$. So $p^{2}$ divides $D$, and consequently, $p$ divides $5p+4$. But $p$ is greater or equal to $7$. Contradiction. So $f(n_{p}) \neq p$. Now assume $f(n_{p})=-1$. The second property now yields \[D = (2p+1)^{2}-4(p+1)^{2};\\ D =-4p-3.\] Now notice that $D$ needs to be positive and that $p$ is positive. So $D$ is negative. Contradiction. So $f(n_{p}) \neq-1$. And if we assume $f(n_{p})=-p$, we get \[D = (p+2)^{2}-4(p+1)^{2};\\ D =-3p^{2}-4p.\] Now notice that $D$ needs to be positive and that $p$ is positive. So $D$ is negative. Contradiction. So $f(n_{p}) \neq-p$. Finally, if we assume $f(n_{p}) =-p^{2}$, after some calculations, we get \[D = (p^{2}+2p+2)^{2}-4(p+1)^{2};\\ D = p^{2}((p-2)^{2}-8).\] Now notice that $D$ needs to be a perfect square and that $p$ is greater or equal to $7$. Now notice that \[(p-3)^{2}= (p-2)^{2}-2(p-2)+1;\\ (p-3)^{2}\leq (p-2)^{2}-9,\] so $(p-3)^{2}< (p-2)^{2}-8 < (p-2)^{2}$. Since $(p-2)^{2}-8$ is not a perfect square, $D$ also is not. Contradiction. So $f(n_{p}) \neq-p^{2}$. Now we proved that $f(n_{p}+1)= (p-1)^{2}$, which is equivalent to $f(n_{p}+1)=(k-n_{p}-1)^{2}$. Note that there are infinitely many primes, thus there are also infinitely many negative integer $n_{p}$ such that $k-n_{p}$ is a positive prime. So all we need to prove now is that if $f(n) = (k-n)^{2}$, $f(n+1) = (k-n-1)^{2}$. This can easily be shown by plugging $f(n) = (k-n)^{2}$ into $f(n)f(n+1)=(f(n)+n-k)^{2}$, for $n \neq k$. So for now, we've proven that $f(n) = (k-n)^{2}$ if $n \leq k$. So assume $n=k$. We've proven our assertion for all $n \leq k$, so $f(k) = 0$. Now notice that $f(k+1)$ divides $1$. Now assume $f(k+1) =-1$. This yields $f(k+2)=0$, and \[f(k+2)f(k+3) = (f(k+2)+k+2-k)^{2}\iff 0 = 4,\] which is a contradiction. So $f(k+1)=1$. So now we've proven for every negative $n$ that $f(n)=(k-n)^{2}$. Now we'll check that this solution works: \[f(n)f(n+1) = (n-k)^{2}(n-k-1)^{2}= ((n-k)^{2}+(n-k))^{2}= (f(n)+n-k)^{2}.\] So $f(n) = (n-k)^{2}$ is the only function that satisfies the conditions. $\Box$

Attachments:
Solution CTST 02 5.tex (5kb)

Anyone got a nicer solution?

Take a large prime $p$, and substitute $n=-p+k$, we get \[f(-p+k)f(-p+k+1)=(f(-p+k)+p)^2\] So $f(-p+k)|p^2$, which means $f(-p+k)=-p^2,-p,-1,1,p,p^2$, and $f(-p+k+1)=-p^2+2p-1,0,-1+2p-p^2,1+2p+p^2,4p,p^2+2p+1$. But we also have $f(-p+k+1)|(p+1)^2$, so $f(-p+k+1)=p^2+2p+1=(p+1)^2$. Hence there are infinitely many $n$ such that $f(n)=(n-k)^2$. Note that if $f(n)=(n-k)^2$, then $f(n+1)=(n+1-k)^2$, therefore $f(n)=(n-k)^2$ for all $n\in\mathbb{Z}^-$, which indeed satisfies the given equation.

The functions that work are $\boxed{f(n)=(n-k)^2}$, if $k=-2$ we also have $\boxed{f(n)=(n-k)^2, k\neq -1,f(-1)=a,a\in\mathbb{Z}}$, and if $k=-3$ we have $\boxed{f(n)=(n-k)^2, k>-2,f(-2)=-1, \text{and } f(-1)=0}$ These solutions can all be verified to work. Notice that $f(n)|(n-k)^2$ for $f(n+1)$ to be an integer. Let $p$ be an arbitrarily large prime and let $n=k-p$. The condition becomes: $$f(k-p)f(k-p+1)=(f(k-p)-p)^2$$For $f(k-p+1)$ to be an integer we must have $f(k-p)\in\{-p^2,-p,-1,1,p,p^2\}$ These give $f(k-p+1)\in\{(p+1)^2,-4p,-(p+1)^2,(p-1)^2,0,(p-1)^2\}$. Since $f(k-p+1)^2|(p-1)^2$ the only possibilities are $f(k-p+1)\in\{0,(p-1)^2\}$, but $f(k-p+1)=0$ doesn't work so we have $f(k-p+1)=(p-1)^2$. But if $f(n)=(n-k)^2\Rightarrow f(n+1)=(n+1-k)^2$ except for $n=k$. If $k\in{-2,-3}$ we get the cases above otherwise $f(k+1)|1\Rightarrow f(k+1)\in{-1,1}$ and we can eliminate the solution of $f(-1)=-1$ and continue our upward induction.