Intereting Posts

When a covering map is finite and connected, there exists a loop none of whose lifts is a loop.
Problem with Abel summation
Index notation for tensors: is the spacing important?
Why is $\arctan(x)=x-x^3/3+x^5/5-x^7/7+\dots$?
Examples of sets whose cardinalities are $\aleph_{n}$, or any large cardinal. (not assuming GCH)
How is the hyperplane bundle cut out of $(\mathbb{C}^{n+1})^\ast \times \mathbb{P}^n$?
Convergence of: $\sum\limits_{n=1}^{\infty} \frac{(-1)^{n+1}\sin(nx)}{n}$
How can I visualize a four-dimensional point inside a Schlegel diagram of a tesseract?
Prove that if $f:A\to B$ is uniformly continuous on $A$ and $g$ is uniformly continuous on $B$, then $g(f(x))$ is uniformly continuous on $A$
Alternative form to express the second derivative of $\zeta (2) $
Does $A\oplus \mathbb{Z}\cong B\oplus \mathbb{Z}$ imply $A\cong B$?
How to find $\lfloor 1/\sqrt{1}+1/\sqrt{2}+\dots+1/\sqrt{100}\rfloor $ without a calculator?
prove that $\frac{(2n)!}{(n!)^2}$ is even if $n$ is a positive integer
No uncountable ordinals without the axiom of choice?
Orthogonal Projection onto the Unit Simplex

If we have a linear homogeneous recurrence relation, such as $t_{k+1}=4t_k-4t_{k-1}$, and attempt to find solutions of the form $t_n=x^n$ for some $x \in \mathbb{R} \setminus \{0\}$, we obtain the characteristic polynomial $(x-2)^2=0$. The characteristic polynomial has repeated roots, so the standard technique is to look for solutions of the form $t_n=nx^n$ too.

It’s routine to check that $t_n=n x^n$ is indeed another solution to the recurrence. But, if I didn’t already know that $t_n=n x^n$ is a solution, why would I think to look at solutions of this form?

Question: What motivation is there to consider solutions such as $t_n=n x^n$ in the case of repeated roots?

- recursion-consecutive numbers
- A Recurrence Relation Involving a Square Root
- Integer partition of n into k parts recurrence
- Recurrence telescoping $T(n) = T(n-1) + 1/n$ and $T(n) = T(n-1) + \log n$
- $W_n=\int_0^{\pi/2}\sin^n(x)\,dx$ Find a relation between $W_{n+2}$ and $W_n$
- Show that ${(F_n^2+F_{n+1}^2+F_{n+2}^2)^2\over F_{n}^4+F_{n+1}^4+F_{n+2}^4}=2$

I find it easy to motivate looking for solutions of the form $t_n=x^n$, since e.g. for the Fibonacci numbers $F(n)$, we can prove exponential upper and lower bounds on $F(n)$, and it seems reasonable to suspect that similar inequalities hold more generally.

- Recurrence relation, Fibonacci numbers
- What is the asymptotic behavior of a linear recurrence relation (equiv: rational g.f.)?
- Solve recurrence equation $T(n)=2T(n-1)-4$
- Recurrence telescoping $T(n) = T(n-1) + 1/n$ and $T(n) = T(n-1) + \log n$
- showing the limit of a recurrence relation
- Links between difference and differential equations?
- Solve the following non-homogeneous recurrence relation:
- Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$
- What is the most elementary way of proving a sequence is free of non-trivial squares?
- How to deduce a closed formula given an equivalent recursive one?

To set the stage, let $V$ be the vector space of sequences $a_0, a_1, … $ (say of elements of an algebraically closed field) indexed by non-negative integers. On this vector space define the *shift operator* $S : V \to V$, which sends a sequence $a_i$ to the sequence $(Sa)_i = a_{i+1}$. To say that $a$ satisfies a linear recurrence with characteristic polynomial $p$ is then precisely to say that

$$p(S) a = 0.$$

Since we’re working over an algebraically closed field, we can factor

$$p(S) = \prod_{i=1}^n (S – \lambda_i I)^{m_i}$$

and then write our recurrence as

$$\prod_{i=1}^n (S – \lambda_i I)^{m_i} a = 0.$$

In particular, any sequence satisfying $(S – \lambda_i I)^{m_i} a = 0$ (a **generalized eigenvector** of $S$ with eigenvector $\lambda_i$) satisfies the recurrence, and standard results in linear algebra imply that generalized eigenvectors span the entire space of solutions.

So it suffices to solve the generalized eigenvector equation. First, I’m not sure if you know this, so it’s worth saying: if $m_i = 1$, then the space of solutions to

$$(S – \lambda_i I) a = 0$$

is spanned by $a_n = \lambda_i^n$ and this is the clearest reason I can think of (eigenvector decomposition) to look for exponential solutions.

Before we tackle the general case, another special case: $\lambda_i = 1$. In this case $S – I$ is just the forward difference operator, and the sequences satisfying

$$(S – I)^n a = 0$$

are precisely the polynomial sequences of degree less than $n$. This should be a familiar fact about the forward difference operator, and it turns out to imply the general result. Indeed, suppose $a$ satisfies

$$(S – \lambda_i I)^n a = 0$$

and write $a_n = \lambda_i^n b_n$ for some sequence $b_n$.

**Lemma:** $((S – \lambda_i I)a)_n = \lambda_i^{n+1} ((S – I)b)_n$.

*Proof.* Straightforward computation.

By induction, it follows that

$$(S – \lambda_i I)^n a = 0 \Leftrightarrow (S – I)^n b = 0$$

and the conclusion follows. (I haven’t discussed the case $\lambda_i = 0$ but the solutions are easy to describe here.)

We’ll work through a simple representative example since the goal here is motivation. Consider a sequence $a$ satisfying $(S – \lambda_1 I)(S – \lambda_2 I) a = 0$ where $\lambda_1 \neq \lambda_2$, and let’s see what happens if we let $\lambda_1 \to \lambda_2$. To take this limit sensibly we’ll fix initial conditions $a_0 = 0, a_1 = 1$. This will give

$$a_n = \frac{\lambda_1^n – \lambda_2^n}{\lambda_1 – \lambda_2}$$

Now taking the limit $\lambda_2 \to \lambda_1$ and applying, for example, l’Hopital’s rule, we obtain

$$a_n = n \lambda_1^{n-1}.$$

The shift operator $S$ defined above has another incarnation as differentiation $D$: indeed, we just need to associate to a sequence $a_0, a_1, …$ the exponential generating function

$$A(t) = \sum_{n=0}^{\infty} a_n \frac{t^n}{n!}.$$

Solutions to $p(S) a = 0$ then become solutions to differential equations $p(D) A = 0$. But now that we can work in the formalism of differential equations we can appeal to physical intuition: in physical terms, the relevant phenomenon is **resonance.** More concretely, let’s work with a forced harmonic oscillator

$$m \frac{d^2 x}{dt^2} + kx = \sin \omega t.$$

(Think of periodically pushing a swing.) Note that $x$ satisfies $(m D^2 + k)(D^2 + \omega^2) x = 0$. This polynomial has repeated roots when $\omega^2 = \frac{m}{k}$, that is, when the frequency of the forcing function matches the “natural frequency” of the system (if physicists have better terms for these I’ve forgotten them). In that case one can observe experimentally in the relevant physical systems (e.g. the Tacoma Narrows bridge) that the amplitude of the oscillations increase linearly with time, and one can observe mathematically that the solution involves terms like $t \sin \omega t$ (and one simple way to see this is to use the limiting argument above). Computing the Taylor series of such solutions then gives the familiar extra factor of $n$.

One way to look at this would be using generating functions.

The generating function comes out to

$$F(x) = \frac{Q(x)}{P(x)}$$

where the polynomial $P(x)$ is got from the characteristic polynomial, by replacing $x$ by $\frac{1}{x}$ and multiplying by an appropriate power of $x$.

Now using the partial fraction decomposition

$$ \frac{Q(x)}{(x-a_1)^{n_1} \dots (x-a_k)^{n_k}} = \sum_{i=1}^{k} \sum_{j=1}^{n_i} \frac{A_{ij}}{(x-a_1)^j}$$

tells us that we should get a polynomial in $n$.

- What is the purpose of the first test in an inductive proof?
- Example for an ideal which is not flat (and explicit witness for this fact)
- “Visualizing” Mathematical Objects – Tips & Tricks
- Prove that any two consecutive terms of the Fibonacci sequence are relatively prime
- What is $iav-\log(v)$? Any series expansion or inequality for it?
- Peano Arithmetic before Gödel
- Is $2^k = 2013…$ for some $k$?
- Definition of injective function
- Eigenvalue decomposition of $D \, A \, D$ with $A$ symmetric and $D$ diagonal
- What REALLY is the modern definition of Euclidean Spaces?
- Does $f(0)=0$ and $\left|f^\prime(x)\right|\leq\left|f(x)\right|$ imply $f(x)=0$?
- Is there a closed form expression for this sum involving Stirling number of second kind
- Proof that $\ln(n^2)(\ln(n) – 1) < n$ for all $n\in\mathbb{N}$
- How can I show that $ab \sim \gcd (a,b) {\operatorname{lcm} (a,b)}$ for any $a,b \in R \setminus \{0\}$?
- How to prove that $\sum _{k=0}^{2n-1} \frac{(-2n)^k}{k!}<0 $