Intereting Posts

Expected number of dice rolls of an unfair dice to roll every side equally many sides
Is every $T_4$ topological space divisible?
Given the permutation $\sigma=\left(\begin{array}{ccccc} 1&2&3&4&5\\ 3&1&2&5&4 \end{array}\right)$
Showing that an algebraic set is not isomorphic to $\mathbb{A}^1$
A local diffeomorphism of Euclidean space that is not a diffeomorphism
Prove QM-AM inequality
Positive integer solutions to $x^2+y^2+x+y+1=xyz$
Why is $\int_{0}^{\infty} \frac {\ln x}{1+x^2} \mathrm{d}x =0$?
Transpose inverse automorphism is not inner
The alternating group is generated by three-cycles
Jordan decomposition of an endomorphism with minimal polynomial
Properties of $\liminf$ and $\limsup$ of sum of sequences: $\limsup s_n + \liminf t_n \leq \limsup (s_n + t_n) \leq \limsup s_n + \limsup t_n$
Binomial Coefficients with fractions
A mathematical phenomenon regarding perfect squares…
homology over fields

Could someone explain what $R(x)$ and constant $c_1,c_2,…,c_k$ are in this article about characteristic polynomial in proof 3?

If that someone could rephrase it, because it seems not so clear in the link provided, I would appreciate it. Could you give me a example?

Thanks in advance!

- Prove that $2^n +1$ in never a perfect cube
- How to calculate percentage of value inside arbitrary range?
- A polynomial determined by two values
- Algorithm for computing square root of a perfect square integer?
- $n^5-n$ is divisible by $10$?
- Sum of absolute values and the absolute value of the sum of these values?

- A riddle for 2015
- Why is the derivative of sine the cosine in radians but not in degrees?
- For $x>0$, $x + \frac1x \ge 2$ and equality holds if and only if $x=1$
- Sum of a Hyper-geometric series. (NBHM 2011)
- Explanation of method for showing that $\frac{0}{0}$ is undefined
- Minimum period of function such that $f\left(x+\frac{13}{42}\right)+f(x)=f\left(x+\frac{1}{6}\right)+f\left(x+\frac{1}{7}\right) $
- Prove that g has no roots
- The same bit of trivial algebra in two different places?
- Why is $i^i$ real?
- Cutting a $m \times n$ rectangle into $a \times b$ smaller rectangular pieces

I’ll take the following problem as an example of how to use generating functions in recurrences:

Let $p_{n+1}=3p_{n}-p_{n-1}$ with $p_0=5,p_1=7$. What is the general form of $p_n$?

Define the following generating function:

$$P(x)=\sum_{n=0}^\infty p_nx^n= p_0+p_1x+p_2x^2+p_3x^3+\cdots.$$

Notice that

$$3P(x)-xP(x)=3p_0+(3p_1-p_0)x+(3p_2-p_1)x^2+(3p_3-p_2)x^3+\cdots.$$

We can simplify this using the recurrence to the following:

$$(3-x)P(x)=3p_0+\color{Blue}{p_2x+p_3x^2+p_4x^3+\cdots}.$$

Now the blue part looks familiar. In fact, it’s just the usual expansion for $P(x)$, but with the first two terms cut off and then the powers of $x$ reduced one, so this is:

$$(3-x)P(x)=3p_0+\frac{P(x)-(p_0+p_1x)}{x}$$

$$\implies [x(3-x)-1]P(x)=(3p_0-p_1)x-p_0.$$

*Remark*: It’s unclear to me whether the AoPS article forgot an initial term or wanted us to subsume the initial $3p_0$ into the fraction in order to form the remainder polynomial $R(x)$. The important fact to take away is that we use the recurrence to simplify the right side involving only $P(x)$ and other basic operations with $x$, specifically as something plus $P(x)$ minus a cut-away divided by a power of $x$. Plug in the initial values for $p_0,p_1$ and divide for

$$P(x)=\frac{8x-5}{-x^2+3x-1}.$$

Now we attempt partial fraction decomposition. The quadratic formula tells us that the roots of the denominator polynomial $x^2-3x+1$ are $u=(3+\sqrt{5})/2$ and $v=(3-\sqrt{5})/2$. We then write:

$$-P(x)=\frac{8x-5}{x^2-3x+1}=\frac{A}{x-u}+\frac{B}{x-v}.$$

Combine the fractions on the right side and focus on numerators to get:

$$8x-5=(A+B)x-(vA+uB)$$

$$\implies \begin{pmatrix}1&1\\v&u\end{pmatrix}\begin{pmatrix}A\\B\end{pmatrix}=\begin{pmatrix}8\\5\end{pmatrix}$$

$$\implies\begin{pmatrix}A\\B\end{pmatrix}=\frac{1}{u-v}\begin{pmatrix}u&-1\\-v&1\end{pmatrix}\begin{pmatrix}8\\5\end{pmatrix}$$

$$=\frac{1}{\sqrt{5}}\begin{pmatrix}+7+4\sqrt{5}\\-7+4\sqrt{5}\end{pmatrix}.$$

Finally, we can expand $P(x)$ using the geometric series formula to get:

$$P(x)=-\frac{A}{x-u}-\frac{B}{x-v}$$

$$=\frac{A/u}{1-x/u}+\frac{B/v}{1-x/v}$$

$$=\sum_{n=0}^\infty \left(Au^{-1-n}+Bv^{-1-n}\right)x^n$$

$$=\sum_{n=0}^\infty\left[ (4+7/\sqrt{5})\left(\frac{3-\sqrt{5}}{2}\right)^{n+1}+(4-7/\sqrt{5})\left(\frac{3+\sqrt{5}}{2}\right)^{n+1}\right]x^n.$$

Note that we used $u^{-1}=v$ and $v^{-1}=u$. The expression inside the square brackets is therefore the formula of $p_n$. Also keep in mind this example is a bit more complicated than usual. Finally, remember that this is an example of a linear recurrence derived using the method described on the AoPS article; it does not apply to the original *non*$\text{}$linear problem you posted.

- Finding when $\mathbb{C}P^n / \mathbb{C}P^{n-2}$ is homotopy equivalent to $S^{2n} \vee S^{2n-2}$ using Steenrod squares
- Why does Arccos(Sin(x)) look like this??
- Can the product $AB$ be computed using only $+, -,$ and reciprocal operators?
- Why is it that Complex Numbers are algebraically closed?
- $f,g$ continuous from $X$ to $Y$. if they are agree on a dense set $A$ of $X$ then they agree on $X$
- Finding nonnegative solutions to an underdetermined linear system
- Prove that $\sqrt{x}$ is continuous on its domain $[0, \infty).$
- Expectation of $QQ^T$ where $Q^TQ=I$
- Convergent or divergent: $\sum_{k=1}^{\infty}\frac{2^{k}\cdot k!}{k^{k}}$
- Proof of Matrix Norm (Inverse Matrix)
- Christoffel symbols and fundamental forms
- Intuition behind Conditional Expectation
- Is $7$ the only prime followed by a cube?
- Proving “every set can be totally ordered” without using Axiom of Choice
- Is there any geometric way to characterize $e$?