Codex @codex  0

For a linear recurrence relation with two distinct characteristic equation of a linear recurrence roots $r_1,r_2$, the solution is $u_n=A{r}_1^n+B{r}_2^n$. If $|r_1|<1<|r_2|$, boundedness for $n\to \infty$ forces $B=0$, and $u_0$ fixes $A$. This selects the decaying discrete mode in a finite difference method for a boundary problem on an unbounded interval. Roots on the unit circle require separate treatment; a repeated root there can contribute an unbounded factor $n$.

Every square matrix satisfies its own characteristic polynomial. More explicitly, for an $n$-by-$n$ matrix $A$ over a commutative ring with identity, formThenHere $0$ is the zero matrix, and the constant term multiplies the identity matrix. This is a polynomial evaluated at a matrix; it is stronger than saying that each eigenvalue is a root of a polynomial. Neither diagonalizability nor distinct eigenvalues is required.^[ref]

The practical payoff is that arbitrarily high matrix powers can be reduced to a combination of $I,A,\dots ,A^{n-1}$. These powers arise when repeatedly applying a linear map, solving a linear recurrence relation, or evolving a finite state space model. The characteristic polynomial turns that repeated action into a fixed-order scalar recurrence. The minimal polynomial may reduce the number of required powers further.

For a constant-coefficient linear recurrence relation, substituting a trial sequence $u_n=r^n$ produces a polynomial equation in $r$ called its characteristic equation. Repeated roots contribute factors polynomial in $n$.

For two solutions of the linear recurrence relation $x_{n+2}+b_n{x}_{n+1}+c_n{x}_n=0$, their discrete Wronskian obeys $W_{n+1}=c_n{W}_n$. Substitute the recurrence into $p_{n+1}{q}_{n+2}-p_{n+2}{q}_{n+1}$: the $b_n$ terms cancel and the remaining expression is $c_n(p_n{q}_{n+1}-p_{n+1}{q}_n)$. Iteration gives $W_{n+1}=W_1{\prod }_{m=1}^n{c}_m$, including when some $c_m$ vanish. A nonzero discrete Wronskian proves linear independence of the two solutions.

Let $E$ be the forward shift on sequences and $P$ the polynomial defining a constant-coefficient linear recurrence relation. For a nonzero base $r$, $P(E)r^n=P(r)r^n$, so $r^n/P(r)$ is a particular solution when $P(r)\ne 0$. At a simple root of the characteristic equation of a linear recurrence, the correct trial acquires a factor $n$:The identity follows by substituting $(n+j)r^{n+j}$ into each shift term. A root of multiplicity $m$ analogously requires a degree-$m$ polynomial factor; the lower-degree homogeneous terms are supplied by the repeated characteristic root of a linear recurrence.

The linear recurrence relation defining the Fibonacci numbers, with $F_0=0$ and $F_1=1$. Its state $(F_{n+1},F_n{)}^T$ advances by the matrix $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$, so matrix powers describe repeated updates.

For the Legendre differential equation $(1-x^2)y^{\prime \prime }-2x{y}^{\prime }+n(n+1)y=0$, put $t=1+x$. The equation becomes $t(2-t)y_{tt}+2(1-t)y_t+n(n+1)y=0$. Its indicial equation is $2r^2=0$. The exponent-zero power series $\sum a_k{t}^k$ obeys the displayed linear recurrence relation. For a nonnegative integer $n$, it terminates at degree $n$, giving a Legendre polynomial with $a_0\ne 0$. Every analytic solution at the endpoint is proportional to this one, since the recurrence determines all coefficients from $a_0$.

The second independent solution has the local form $P_n(x)\log (1+x)+B(x)$, where $B$ is analytic near $-1$. Indeed, reduction of order gives $P_n(x)\int dx/[(1-x^2)P_n(x{)}^2]$, whose integrand is $1/[2P_n(-1{)}^2(1+x)]$ plus an analytic function. Rescale the second solution to obtain the unit coefficient of $P_n\log (1+x)$. Reflection gives the corresponding expansion at $x=1$. This also proves the logarithmic divergence of the independent Legendre function of the second kind at each endpoint.

An inhomogeneous linear recurrence has a prescribed forcing sequence $g_n$ rather than zero on the right. The difference of two solutions satisfies the associated homogeneous linear recurrence relation, so every solution is a particular solution plus a homogeneous solution.

Consider a random walk on $\{0,1,\dots ,n\}$ with absorbing states $0,n$. At each interior state it stays in place with probability $q$, and moves one position in either direction with probability $(1-q)/2$, where $0\le q<1$. Its mean absorption time from $k$ isProof. A sequence of at most $n$ consecutive leftward moves ensures absorption, with probability at least $((1-q)/2{)}^n>0$. Dividing time into blocks of length $n$ gives a geometric series bound on the survival probabilities, so the expected value is finite. Let $e_k={\mathbb{E}}_k[T]$. The law of total expectation and first-step analysis giveThus $e_{k+1}-2e_k+e_{k-1}=-2/(1-q)$. A particular solution of this linear recurrence relation is $-k^2/(1-q)$; its homogeneous solutions are $A+Bk$. The two boundary conditions give $A=0$, $B=n/(1-q)$, proving both the formula and its uniqueness. Holding slows the usual symmetric random walk by the factor $1/(1-q)$.

A second-order linear recurrence relation normally uses two consecutive initial conditions, but two specified nonconsecutive values may also determine a unique solution of the linear recurrence relation. For two independent homogeneous solutions of the linear recurrence relation $v_n,w_n$, the coefficients in $u_n=u_n^{\mathrm{p}}+A{v}_n+B{w}_n$ are determined by $u_j,u_k$ exactly when $v_j{w}_k-v_k{w}_j\ne 0$. Otherwise the data can be inconsistent or can leave freedom. A nonconsecutive subscript is therefore not by itself evidence of an error.

For a repeated characteristic root of a linear recurrence $r\ne 0$, use $v_n=r^n$, $w_n=n{r}^n$. The determinant is $(k-j)r^{j+k}\ne 0$ for distinct $j,k$, so any such pair of prescribed values determines the two coefficients.

Use $t=x+1$. The Legendre differential equation becomesSubstituting a Frobenius series $y=t^r{\sum }_{k\ge 0}{a}_k{t}^k$, $a_0\ne 0$, gives the indicial equation $2r^2=0$: the indicial root zero is repeated. For $r=0$, the coefficient of $t^k$ yieldsorFor $0\le k<n$ the multiplying factor is nonzero. At $k=n$ it vanishes, so $a_{n+1}$ and all later coefficients are zero. Thus one solution is a polynomial of exact polynomial degree $n$, including a nonzero constant when $n=0$. Denote a chosen normalization by $P_n$.

The linear recurrence relation determines every analytic coefficient from $a_0$, so there cannot be a second independent analytic solution at $t=0$. To see the required logarithm explicitly, reduction of order gives the second solution locally asNear $t=0$, the integrand is $1/(2a_0^{2}t)$ plus an analytic function. After rescaling the second solution, its form is thereforeThe analytic remainder converges locally; its constant term may be set to zero by adding a multiple of $P_n$. The nonzero logarithmic coefficient makes $y_2$ linearly independent of $P_n$. This Frobenius expansion of the Legendre equation at an endpoint gives a Logarithmic Frobenius solution; the same endpoint calculation at $x=1$ explains why the independent Legendre function of the second kind is excluded when boundedness at both ends is required.

For the homogeneous linear recurrence relation, substitute $y_k=r^k$. Its characteristic equation of a linear recurrence is $r^2-r+1=0$, with roots $e^{i\pi /3}$ and $e^{-i\pi /3}$. Taking real linear combinations givesThese two real sequences are linearly independent: their values at $k=1,2$ form a matrix with determinant $\sqrt{3}/2\ne 0$. Thus their two constants account uniquely for arbitrary first two values.

Let $P_k={\sum }_{n=1}^k{a}_n/(k-n+1)$ and reindex as $P_k={\sum }_{j=1}^k{a}_{k-j+1}/j$. In $P_{k+2}-P_{k+1}+P_k$, each term with $1\le j\le k$ has coefficientThe term $j=k+1$ is $(a_2-a_1)/(k+1)=0$, and the remaining term is $a_1/(k+2)=1/(k+2)$. This explicitly proves that $P_k$ is the required particular solution, a discrete Green convolution for the period-six recurrence.

The unit-response coefficients have the homogeneous form just found. The values $a_1=a_2=1$ give zero cosine coefficient and sine coefficient $2/\sqrt{3}$, soSubtracting this particular solution from any other solution leaves a homogeneous recurrence. Thus the complete answer is

Substitute the linear recurrence relation for each of $p_{n+2}$ and $q_{n+2}$ in the discrete Wronskian:Iterating givesNo division was used, so vanishing $c(m)$ cause no exception.

For constant coefficients, seek a solution $x_n=r^n$. The characteristic equation of a linear recurrence is $r^2+\alpha r+1=0$. Choose $\theta \in [0,\pi ]$ with $\cos \theta =-\alpha /2$. Its roots are $r=e^{i\theta }$ and $e^{-i\theta }$, since $r+r^{-1}=2\cos \theta$. For the two resulting solutions,It is independent of $n$, exactly as the product identity predicts when $c(n)=1$.

When $-2<\alpha <2$ the roots are distinct and the discrete Wronskian is nonzero. At $\alpha =-2$ or $2$, the two displayed solutions coincide and $W_n=0$; the identity still holds. If an independent pair is wanted at these endpoints, take $r^n$ and $n{r}^n$, where $r=1$ or $-1$ respectively. Direct substitution verifies both, and their discrete Wronskian is $r^{2n+1}=r\ne 0$.

The transition row sums to one, since $p{\sum }_{k=0}^i{q}^k+q^{i+1}=1$. From any state the Markov chain can reach zero, and from zero consecutive upward moves reach every state; hence it is irreducible. Its self-transition at zero has probability $q>0$, so it is aperiodic. It is the reflected chain with geometric downward jumps.

Put $h_0=1$ for the hitting problem. The first-step equations for $i\ge 1$ areSubtracting $q$ times the equation at $i-1$ gives the linear recurrence relation, valid for $i\ge 2$,The separate boundary equation at $i=1$ is $h_1=q^2+pq{h}_1+p{h}_2$. It must not be replaced by the linear recurrence relation with $h_0=1$: the absorbing hitting convention at zero is different from applying a first-step return equation there.

For $p\ne q$, the linear recurrence relation has roots $1$ and $r=q/p$, so $h_i=A+B{r}^i$ for $i\ge 1$. The boundary equation gives $B=r(1-A)$. If $p<1/2$, then $r>1$ and boundedness of probabilities forces $B=0$, hence $A=1$. If $p=1/2$, the repeated-root solution is $A+Bi$; boundedness again gives $B=0$ and the boundary equation gives $A=1$.

For $p>1/2$, $r<1$ and the nonnegative harmonic candidate ${\tilde{h}}_i=r^{i+1}$, together with ${\tilde{h}}_0=1$, satisfies every first-step equation. Hitting-by-time-$n$ probabilities start from zero off the target and iterate those equations, so by induction they are bounded above by this candidate. Taking their increasing limit gives $h_i\le r^{i+1}$. But the general bounded solution has limit $A\ge 0$ as $i\to \infty$, forcing $A=0$ under that bound. ThusIn particular the transient exponent is $i+1$, fixed by the original boundary equation.

The probability of a subsequent return to zero when starting there is $f_{00}=q+p{h}_1$. It is one for $p\le 1/2$, so the Markov chain is recurrent there. For $p>1/2$ it equals $q+p(q/p{)}^2=q/p<1$, so the irreducible Markov chain is transient.

For a stationary probability vector $\pi$, balance at zero and one gives ${\pi }_1=(p/q){\pi }_0$. Subtracting adjacent balance equations givesso this initial ratio propagates and ${\pi }_j={\pi }_0(p/q{)}^j$. It can be normalized only when $p<q$. In that caseDirect substitution verifies all balance equations, including ${\pi }_0=q{\sum }_i{\pi }_i{q}^i$. An irreducible Markov chain admitting this stationary probability law is positive recurrent, with mean return time $1/{\pi }_0=q/(q-p)$. At $p=q$ the linear recurrence relation and boundary relation force every ${\pi }_j$ equal; no such nonzero sequence is summable. The recurrent chain is therefore null recurrent. In summary,

The homogeneous sequences are again $(-2{)}^k$ and $(-3{)}^k$. A particular solution $D{2}^k$ has left-hand side $10D{2}^k$, so $D=1/10$. Consequently $y_k=A(-2{)}^k+B(-3{)}^k+2^k/10$. The two initial conditions require $A+B=9/10$ and $-2A-3B=4/5$, giving $A=7/2$ and $B=-13/5$. ThusThe linear recurrence relation can be rearranged as $y_{k+1}=2^k-5y_k-6y_{k-1}$. Starting with the two integer values, mathematical induction proves that every $y_k$ for $k\ge 0$ is an integer. For $n\ge 1$, the closed form givesThe first term on the right is divisible by ten; the second is too, because $(-2{)}^n$ supplies a factor two and $35$ supplies a factor five. Therefore $10$ divides $2^n-26(-3{)}^n$ for every positive integer $n$. The positivity condition matters: at $n=0$ the expression is $-25$.

For the homogeneous linear recurrence relation, a trial $u_k=r^k$ gives the characteristic equation of a linear recurrence $r^2+5r+6=(r+2)(r+3)=0$. Thus the two homogeneous sequences are $(-2{)}^k$ and $(-3{)}^k$. Seek a particular solution $u_k=ak+b$; substitution gives $12ak+12b-5a=12k+1$, so $a=1$ and $b=1/2$. HenceThe two independent constants supply arbitrary initial values for this second-order linear recurrence relation.

False. Take $s_{n+1}=s_n$ and $t_{n+2}=t_{n+1}+t_n$. The only nonzero length-one fill produces constant ones. Constant ones cannot satisfy the second linear recurrence relation, since $1+1=0$ in ${\mathbb{F}}_2$. Thus these linear-feedback shift registers have no identical outputs from nonzero fills.

Let $L[y{]}_n=y_{n+3}-3y_{n+1}+2y_n$. For the exponential trial sequence $D{2}^n$,Thus $D=1/4$ gives a particular solution. The difference of any two solutions of the inhomogeneous linear recurrence satisfies the homogeneous linear recurrence relation in part (i). Therefore

Substitution of $y_n=r^n$ gives the characteristic equation of a linear recurrenceThe repeated characteristic root of a linear recurrence $1$ supplies the solutions $1$ and $n$, while the simple root $-2$ supplies $(-2{)}^n$. They are linearly independent: their values at three consecutive indices have nonzero determinant. A third-order linear recurrence relation is uniquely determined by three consecutive initial values, so these three solutions span its solution space. The general solution is

The superposition principle applies because the recurrence operator is linear. Add the particular solutions from parts (ii) and (iii), then add the general homogeneous linear recurrence relation solution from part (i). This gives