Proof that 1d lattice displacement by phonons is given $u_{n\pm 1}(t) = A_ke^{i\omega_k t} e^{i knd}e^{\pm i k d}$ I looked in «Kittel - Introduction to solid state physics», Wikipedia and Google for the derivation that: A phonon of wavenumber $k$ displaces the $s$-th atom in a monoatomic 1d crystal lattice by a distance $u(s,k)$ given by:
$$u_{n\pm 1}(t) = A_ke^{i\omega_k t} e^{i knd}e^{\pm i k d}$$
The first two of the above sources write down the equation of motion 
$$
m \frac{\partial ^2}{\partial t^2}u_s = C(u_{s+1} + u_{s-1} - 2u_{s}),
$$ 
where $m$ is the mass of the $s$-atom and $C$ is the spring constant.
Kittel then goes on by  just writing down the solution without going through the math, saying that it is the solution of a difference equation. Wikipedia on the other hand excuses itself by «This requires significant manipulation using the orthonormality and completeness relations of the discrete Fourier transform», and then chickens out by writing down the solution. But the internet needs to see the proof. 
I hoped that someone would kindly prove the above formula, hopefully thoroughly, using first principles from Calculus, Fourier analysis, real analysis, classical mechanics, Newtonian mechanics, linear algebra, theory of ode and difference equations. I haven't used Fourier analysis for about a year, so when any theorems are used, it'd be great to mark it in the derivation. To me it seems that one way is skip Fourier analysis and instead solve the ode and difference equation, but I don't know how to do it.
This is the FULL description of the problem.
 A: I guess, as Peter Diehr put it, it would be best if you would take out your pencil. So to help you on this, I have formulated the following questions to walk you through the problem :
Preliminary work :

*

*What is the definition of the discrete Fourier transform for $u_n$?


 Actually wikipedia gives it :
 $$ u_n(t) = \sum_{k=1}^{N} U_k(t)~ e^{iknd}$$

2)What is the definition of the inverse transform (i.e. $U_k = f(u_n)$?

 wikipedia gives it too (just need a small tweak to adapt it to our problem) : https://en.wikipedia.org/wiki/Discrete_Fourier_transform
$$ U_k(t) = \frac{1}{N} \sum_{n=1}^{N} u_n(t)~ e^{-iknd}$$



*What is the periodic condition on the position (crucial)? We suppose that the atoms are uniformly distributed (the average positions of two consecutive atoms are separated by a distance $d$, hence the $d$ in the wikipedia definition of the Fourier transform).

Without periodicity, the Fourier transform would make no sense.

 $x(1)=0=x(d(N+1)) \Rightarrow \exp(-ix(1))=\exp(-ix(d(N+1)))=1$. Actually it is better to write the Fourier transform with $\exp\left(\frac{-2i\pi nd}{N}\right)$ than with $e^{iknd}$ to clearly express the periodicity (same wise for the inverse transform). Also, it is more standard to express the sum from $0$ to $N-1$ instead of $1$ to $N$.

4)Orthogonality condition : What is the result of the following sum ?
$$ \frac{1}{N} \sum_{n=0}^{N-1} \exp(-iknd) \exp(-ik' nd)$$

 Tip : Two cases : a) $k=k'$ and b) $k\neq k'$ (use geometric series)

Back to the problem :
Using the Fourier transform of $u_n$ and the equation of motion, you should get (simple complexe trigonometry -- please excuse the pun -- and substitution) :
$$ 2 C \sum_{k=1}^{N} U_k ~ \left(\cos(kd) - 1\right) ~ \exp(iknd) = m~\sum_{k=1}^{N} \frac{d^2U_k}{{dt}^2} \exp(iknd) $$
Do you also feel the urge to take out the summation symbol? This where the orthogonality comes in! Actually, in order to take out the summation symbol, you need to... sum.
step 1 : multiply the equation by $\exp(-ik'nd)$
step 2 : what summation are we supposed to do? It is better if you figure it without looking at the spoiler --- think of our preliminary work, especially question 4).

 $\sum_{n=1}^{N}$ on both side => orthogonality leaves one result, the equation for $k=k'$

Final solution :
Solve :
$$ 2C~U_k ~ \left(\cos(kd) - 1\right) = m~ \frac{d^2U_k}{{dt}^2}  $$

 wikipedia gives the answer : https://en.wikipedia.org/wiki/Phonon. Don't forget that $kd$ is a constant for a given $k$ (therefore for each equation).

Edit (for solving this question) :
So the solution is of course of the form :
$$
U_k = A_k e^{i\omega_kt}
$$
And if the system is excited at one of its normal modes (frequencies $\nu_k = \frac{\omega_k}{2\pi}$), the displacement reduces to just one component :
$$
 u_n = A_k e^{i \left(\omega_k t + knd \right)}
$$
and there is a phase shift of $e^{\pm ikd}$ between two consecutive knots of the chain.
$$
 u_{n+1}=u_n e^{ikd}
$$
A: You start by solving the recurrence relation; this can be pretty messy, and Kittel skips it as it doesn't contribute to the physical discussion. The physics has already been captured in the development of the equation. 
All about solving recurrence relationships: < https://en.m.wikipedia.org/wiki/Recurrence_relation>
