Substitution of $y_n={\lambda }^n$ into the linear recurrence relation gives ${\lambda }^{n}p(\lambda )=0$. Since $\lambda \ne 0$, division by ${\lambda }^n$ proves the sequence is a solution exactly when $p(\lambda )=0$.

For a nonzero triple root of a polynomial $\mu$, the repeated characteristic root of a linear recurrence rule gives the three independent solutions ${\mu }^n,n{\mu }^n,n^2{\mu }^n$. One way to see the polynomial factors is to write $y_n={\mu }^n{z}_n$: the recurrence becomes the third forward difference operator applied to $z_n$ equal to zero, so $z_n$ is a quadratic polynomial. ThusThese three constants give arbitrary initial values $y_0,y_1,y_2$, hence the full third-order solution. If $\mu =0$, the recurrence instead reduces to $y_{n+3}=0$: the first three values are arbitrary and every subsequent value is zero. The nonzero-root formula must not be used to discard those initial values.

Normalization of the probability density function givesThe first two moments areConsequentlyThe cumulative distribution function is $F(\varphi )=\varphi /\pi -{\varphi }^2/(4{\pi }^2)=1-(1-\varphi /(2\pi ){)}^2$ on $[0,2\pi ]$. For $U$ with the uniform distribution on $(0,1)$, inverse transform sampling therefore usesThe inverse lies in the required interval and satisfies $F(\Phi )=U$.

Now the event is to hit $20$ before $1$, starting at $3$. Up to the first of those two hitting times, translate the interval by one unit; its endpoints become $0,19$ and the starting point becomes $2$. The gambler's ruin hitting probability is thereforeStopping at $1$ is essential: using the original absorbing endpoint $0$ would answer a different event.

The initial position is $k=17$. Applying the gambler's ruin hitting probability and mean hitting time givesFor comparison, the original central starting position $k=10$ would give probability $1/2$ and mean time $100$ minutes.

The homogeneous linear recurrence relation has characteristic polynomial $(\lambda -1{)}^2$, hence general solution $h_k=A+Bk$. For the expected-time recurrence, rearrangement gives $m_{k+1}-2m_k+m_{k-1}=-2$, for which $-k^2$ is a particular solution. ThusImposing the absorbing boundary conditions from the preceding parts gives the gambler's ruin formulas

Let $m_k$ be the expected remaining hitting time of either endpoint, measured in minutes. The first step consumes one minute, after which first-step analysis givesThe expectation is finite: from any interior state, a block of twenty leftward steps guarantees absorption and has probability $2^{-20}$. Thus the survival probability over successive twenty-step blocks has a geometric upper bound. This justifies using finite expectations in the recurrence.

Let $h_k$ be the hitting probability of the right endpoint before the left endpoint, starting at $k$. A surviving vase corresponds to that right-endpoint event. Conditioning on the first step of the simple symmetric random walk givesThe Markov property makes the remaining probability depend only on the position after that step. These absorbing endpoint values distinguish the event of interest from its complement.

Each waiting time has the geometric distribution on $1,2,\dots$ with success probability $1/2$: a wait of length $n$ consists of $n-1$ failures followed by the prescribed success, so its probability is $2^{-n}$. HenceDisjoint successive blocks of independent tosses give independent waiting times. More explicitly, any specified list of block lengths determines exactly one allowed sequence of heads and tails and has probability $2^{-{\sum }_j(h_j+t_j)}$, the product of the individual block probabilities.

There are $2r$ waiting times. Multiplication of their probability generating functions and addition of their expectations giveTo recover its probability mass function, expand by the negative binomial series:The coefficient of $s^n$ is thereforeand it is zero below $2r$. Equivalently there are $\left(\genfrac{}{}{0ex}{}{n-1}{2r-1}\right)$ compositions of $n$ into $2r$ positive block lengths, each with probability $2^{-n}$. This is the negative binomial distribution for a sum of geometric waiting times, even though the desired outcome alternates between blocks.

For $r=1$,Since $\mathbb{E}{Y}_1=4$, Markov's inequality gives $\mathbb{P}(Y_1\ge 5)\le 4/5$, and indeed $5/16<4/5$.

For any nonnegative random variable $X$ with finite expectation and any $a>0$, Markov's inequality statesIndeed $X\ge a{1}_{\{X\ge a\}}$, and taking expectations proves the bound. Nonnegativity is essential.

First, for $0<x<1$, the derivative of $h(x)=\log (1-x)+x$ is $-x/(1-x)<0$, while $h(0)=0$. Hence $\log (1-x)<-x$.

Choose $N>c$ large enough that the given ratio bound holds for every $n\ge N$. Positivity permits taking logarithms, and the preceding inequality givesSumming, and using the integral test for convergence from part (b), gives for $n>N$Thus $a_n\le a_N{N}^c{n}^{-c}$. Since $c>1$, the P-series $\sum n^{-c}$ converges, so the comparison test for series provesThe finitely many initial terms do not affect convergence. This power-law comparison from a refined ratio bound supplies information when the ordinary ratio test can be inconclusive.

The function $1/x$ is decreasing and positive. Therefore on $[k,k+1]$ it is at most $1/k$, and the Riemann integral givesSumming from $k=1$ to $n-1$ yieldsFor $n=1$ both sides are zero; for $n>1$ the inequality is actually strict. The same integral test for convergence gives ${\sum }_{k=N}^{n-1}1/k\ge \log (n/N)$.

For a positive-term series, the ratio test says that if $a_{n+1}/a_n\to L<1$, the series converges; if the ratio tends to $L>1$, including positive infinity, it diverges. More generally $\mathrm{limsup}{a}_{n+1}/a_n<1$ suffices for convergence and $\mathrm{liminf}{a}_{n+1}/a_n>1$ for divergence. A limiting ratio of one gives no conclusion.

The P-series $\sum n^{-2}$ converges and the harmonic series $\sum n^{-1}$ diverges. Both have strictly decreasing positive terms, and their successive ratios, $(n/(n+1){)}^2$ and $n/(n+1)$, tend to one. These supply the two requested possibilities.

For a real antisymmetric matrix, $A^T=-A$, so $(A^2{)}^T=A^2$. The previous result makes every eigenvalue $\eta$ of $A^2$ real, with a real nonzero eigenvector $v$. Moreover,Thus every eigenvalue of $A^2$ is real and nonpositive.

Take real unit eigenvectors $u,w$ of $A^2$ for the respective distinct nonzero eigenvalues $-{\lambda }^2,-{\mu }^2$, where the real parameters $\lambda ,\mu$ are nonzero. DefineThe displayed quadratic identity gives $|u^{\prime }|=|w^{\prime }|=1$. Also $u\cdot Au=0$ and $w\cdot Aw=0$, because a real antisymmetric matrix has zero quadratic form. Thus $u\perp u^{\prime }$ and $w\perp w^{\prime }$. Since $A$ commutes with $A^2$, $u^{\prime }$ lies in the same eigenspace of $A^2$ as $u$, and $w^{\prime }$ in the same one as $w$. Distinct eigenspaces of the real symmetric matrix $A^2$ are orthogonal, so all four vectors are orthonormal. Finally,Thus on each of the two perpendicular planes, $A$ acts as a scaled quarter-turn. This constructs the required vectors, rather than merely counting dimensions.

Use the eigenvector basis $v_1=(-1,0,1{)}^T$, $v_2=(1,1,0{)}^T$, $v_3=(1,1,1{)}^T$. The forcing has decomposition $b=-v_1+3v_3$. If $x=c_1{v}_1+c_2{v}_2+c_3{v}_3$, the linear system reduces toFor $\lambda =0$, all coefficients are determined, givingFor $\lambda =1$, the first equation would say $0=-1$, so there are no solutions. For $\lambda =2$, $c_1=1$, $c_3=3$, and $c_2$ is arbitrary. Thus all solutions areThese outcomes illustrate respectively an invertible matrix, incompatible forcing outside its image of a linear map, and a compatible forcing with a nontrivial kernel of a linear map.