In what follows, w will be shorthand for sx. Let y(x) = xw. Evaluate y′ and get (rx+s)w. Let's try to generalize this.
Let y(x) = (x:k)w. Evaluate at x+1 and the factors internal to (x:k) shift upwards. This is multiplied by sx+1, then we need subtract (x:k)sx. Pull w out, and look at what remains.
(x+1)×(x:k-1)/k×s - (x:k)
Add and subtract (x:k-1)s. When subtracting, write this as k×(x:k-1)/k×s. The k joins x+1 to make x-k+1, thus resurrecting (x:k).
(x:k)s - (x:k) + (x:k-1)s
(x:k)r + (x:k-1)s
Bring w back in and get this.
y′ = ((x:k)r + (x:k-1)s) × w
If w is multiplied by a linear combination of binomial coefficients, apply the above formula term by term. Split each term into two, one with a factor of r and one with a lesser degree and a factor of s. This lets us derive the following.
y′′ = ((x:k)r2 + 2(x:k-1)rs + (x:k-2)s2) × w
y′′′ = ((x:k)r3 + 3(x:k-1)r2s + 3(x:k-2)rs2 + (x:k-3)s3) × w
This will remind you of the binomial theorem. Factors of r build up at one end and factors of s build up at the other. I'm going to call the entire sum (without w) a "difference expression", because they result from taking successive differences of y.
Some of these difference expressions will be truncated. If k = 2, then (x:k-2) = 1, and there are no terms beyond this point. You'll not see an s3.
Yes, all this does have a purpose, as we'll see below.
Let ai be the coefficient on the ith term in the difference equation. Thus the equation is a0y + a1y′ + a2y′′ + … up to an times the nth difference. The characteristic polynomial p(u) is anun + an-1un-1 + … + a2u2 + a1u + a0. This has n roots in the complex plane, although some of the roots may be duplicated.
Let r be such a root, and let s = r+1. Let w = sx, and start by setting y = w. Evaluate the ith difference and get riy. This is multiplied by ai. Factor out y, and find p(r)×y, which drops to 0. The difference equation is satisfied, and sx is a solution.
For example, 0 could be a root, if there is no y term. This tells us the constant function 1x is a solution, and indeed, all the difference sequences drop to 0, and 1 is a solution.
If r = -1 we have a problem. The solution is 0x, which is trivial. Try y′ = -y as an example, with an initial condition of y(0) = 1. Set y(1) = 0, so that y′(0) = -1, as it should. Thereafter, set y(x) = 0. This gives a nontrivial solution that is not exponential. The differences at 0 alternate between 1 and -1, while the differences for x > 0 are all 0. At x = 0 the difference equation becomes p(-1), which is 0, and for x > 0 everything drops to 0, so we're ok. This is the only oddball solution, and there is nothing like it in the world of differential equations. I will call this a truncated solution, where y(x) drops to 0 and stays there.
Assume r (other than -1) is a double root, and let y = xw. Again, w is in every term, and pulls out of the equation. Now each difference, starting with the nth order difference, produces its own expression, which looks like the binomial theorem, possibly truncated. Group the first term in each of these difference expressions together to get p(r)×x. This drops to 0.
The second term in each expression is divisible by s; we can factor that out. We are left with: nanrn-1 + (n-1)an-1rn-2 + … + 2a2r + a1. This is the derivative of p, evaluated at r. Review the theory of formal derivatives. When r is a multiple root, p′(r) = 0. Thus the second terms from the difference expressions sum to zero. With k = 1, the terms beyond (x:k-1) are not present, and that completes the proof. When r is a root with multiplicity, xw is a solution.
Next suppose r has multiplicity 3 or higher. Let y = (x:2)w. The lead terms of the difference expressions sum to p(r)×(x:2), which is 0. Group the second terms together and get p′(r)xs, which is also 0. This time the third terms are present. Gather them together, factor out s2, multiply by 2, and get this.
n(n-1)anrn-2 + (n-1)(n-2)an-1rn-3 + … + 12a4r2 + 6a3r + 2a2
This is p′′(r), which is 0 when r has multiplicity ≥ 3. The expressions truncate at this poin, hence (x:2)w is a solution.
If r has multiplicity at least 4, let y = (x:3)w. The first, second, and third terms of the difference expressions regroup, as they did before, giving p(r), p′(r), and p′′(r), which drop to 0. Group the fourth terms together, factor out s3, multiply by 6, and find a sum equal to p′′′(r), which is 0. The pattern continues up to (x:m-1)w, if r has multiplicity m.
Now for that pesky root -1, with multiplicity m. Let y(x) = 0, except for y(m-1) = 1. Taking the differences at x = m-1 alternates between 1 and -1, just as it did before when x was 0. If the characteristic polynomial p(u) has root -1, with factor u+1, then evaluation at x = m-1 yields -1+1, or 0, and there is no trouble.
Notice that the alternating sequence of 1 and -1 agrees with the coefficients of 1/(1+v). Look at the differences to the left, at m-2. Since y(m-2) is 0 by definition, y′(m-2) has to be 1. To get y′′(m-2), subtract y′(m-1)-y′(m-2), giving -2. Follow this up the line, and we are essentially dividing the series 1/(1+v) by 1+v, and shifting it up one level. Therefore the differences at m-2 are the coefficients on v/(1+v)2. By induction, the differences at m-j are the coefficients on vj-1/(1+v)j.
We already showed y solves the differential equation for x = m-1 and beyond. Let's look at x = m-j. Since p has m factors of u+1, it certainly has j factors, and if the differences of y cause (u+1)j to drop to 0 then they satisfy p(u), as mandated by the difference equation. The differences are 0, except for the last two, which are 1 and -j. Expand (u+1)j by the binomial theorem, replace uj with -j, replace uj-1 with 1, and replace the lower powers of u with 0, corresponding to the differences through level j at x = m-j. The expression drops to 0, p(u) becomes 0, and we have a solution.
When the root -1 has multiplicity m there are m linearly independent solutions. The jth solution sets y(m-j) = 1, while y is 0 elsewhere. Combine these, and any finite vector of length m, followed by zeros, is a solution.
Whether the root is -1 or not, the number of distinct solutions equals the multiplicity of each root, hence the number of solutions is n. These are all linearly independent, (we'll prove this below), thus producing an n dimensional vector space of solutions. By the dimensionality theorem, we have found all the solutions to our difference equation.
The functions that form our basis are pure exponentials sx, (including 1x), exponentials with polynomial modifiers (e.g. (x:3)sx), and the truncated functions associated with the root -1.
The jth truncated function is 0 everywhere, except for a 1 in position j. Clearly these are linearly independent.
Suppose a linear combination of functions yields 0, and it employs truncated functions. Subtract these and find a linear combination that yields 0 after some finite index f. We will prove such a linear combination of functions cannot exist.
Suppose all the functions in our linear combination are pure exponentials. Evaluate sif+j, as i runs from 1 to n, and as j runs from 1 to n. all the exponential functions are evaluated at the points f+1 through f+n. This builds an n×n matrix that is vandermonde, and nonsingular. Therefore these functions are linearly independent.
Suppose there is one exponential with several modifiers. Since sx is everywhere nonzero, divide through by sx to find a linear combination of functions (x:j). This builds a polynomial that has finitely many roots, and cannot be 0 after f.
At this point our linear combination has more than one exponential, and at least one of these exponentials is modified by (x:j). Select a linear combination that has the smallest modifier (x:m), and the fewest number of exponentials carrying this modifier.
If our linear combination of functions is 0 beyond f, the same is true of the difference sequence. Remember that (x:j)sx becomes r(x:j)sx + s(x:j-1)sx. Polynomials drop in degree, pure exponentials are multiplied by r, and modified exponentials experience mitosis.
Suppose (x:m) is the highest multiplicity. If the only representative is a polynomial, it has become (x:m-1), and we have a linear combination with lesser multiplicity, which is a contradiction.
There is at least one exponential associated with (x:m); call it (x:m)sx. Let c1 be the original linear combination of functions, and let c2 be the difference sequence. Both contain the basis function (x:m)sx. Let c3 = c1 - c2/r. Notice that the term (x:m)sx drops out. Thus c3 has fewer terms modified by (x:m), or it has no terms based on (x:m). Either way we have a contradiction, since m is minimal, and the number of terms with (x:m) is minimal. However, we still need to prove c3 is nontrivial.
Remember that c1 is based on more than one exponential. consider any other exponential in c1, such as tx. Assume t ≠ 1. This is multiplied by t-1 in c2, and 1-(t-1)/(s-1) in c3. In other words, the term persists in c3, giving a nontrivial linear combination. If t = 1, the term is simply (x:j). The highest term (x:j) drops out of c2, hence it remains in c3.
In all cases, c3 is a nontrivial linear combination that is 0 after f, and violates our selection criteria. The pathological linear combination c1 cannot exist, and these functions are linearly independent. The existence of n different solutions, drawn from distinct basis functions, builds an n dimensional solution space, and completely solves the difference equation with constant coefficients.
In the introduction, we expressed the 7th order difference sequence of y, evaluated at x, as a linear combination of y(x) through y(x+7). Use this to substitute for y(x+7) in e. Now e is a linear combination of y(x) through y(x+6), and the 7th difference of y. Next, write the 6th difference as a linear combination of y(x) through y(x+6), and substitute for y(x+6) in e. Repeat this process, replacing y(x+5) through y(x+1). The result is a traditional difference equation, with constant coefficients, whose solutions have been characterized above. The order of the equation, and the dimension of the solution space, is equal to the maximum phase shift.
Consider the equation y(x) = y(x+4). The solution space has 4 dimensions, according to the values of y(0) through y(3). After that the sequence repeats. Let's solve this using the procedure outlined above.
Set y = sx, and we have sx = sx+4, or 1 = s4. Let s = ±1 or ±i and find four independent solutions. In other words, the vectors {1,1,1,1}, {1,-1,1,-1}, {1,i,-1,-i}, and {1,-i,-1,i} are linearly independent. These basis functions combine to create every solution to y(x) = y(x+4).
Since the above is an iff proposition, a phase shift equation that does not look like y(x+n) = y(x) cannot be periodic.