Problem
ALG-B3-M06-P011 Quadratic Equation on Integers
#11
★★★★☆ Level 4 of 5
Let \(f:\mathbb Z\to\mathbb Z\), \(f(0)=0\), \(f(1)=1\), and \(f(m+n)+f(m-n)=2f(m)+2f(n)\). Prove that \(f(n)=n^2\).
Put \(n=1\) and get a second-order recurrence.
With \(n=1\), \(f(m+1)+f(m-1)=2f(m)+2\). Hence \(f(m+1)-f(m)=f(m)-f(m-1)+2\). Let \(d_m=f(m)-f(m-1)\). Then \(d_{m+1}=d_m+2\), and \(d_1=f(1)-f(0)=1\). Thus \(d_m=2m-1\) for positive \(m\), and summing gives \(f(n)=1+3+\cdots+(2n-1)=n^2\). For negative \(n\), the equation with \(m=0\) gives \(f(-n)=f(n)\). Therefore \(f(n)=n^2\) for all integers \(n\).
Full proof of the quadratic template on \(\mathbb Z\).