Intereting Posts

Series convergence proof review (Baby Rudin)
Recurrence with varying coefficient
Approximation by smooth function while preserving the zero set
How to find the closed form of the integral$\int_{0}^{\infty}f(x)\frac{\sin^nx}{x^m}dx$
Does the order of “unbounded” quantifiers matter?
Proof for convergence of a given progression $a_n := n^n / n!$
Krull-Akizuki theorem without Axiom of Choice
Proving that $\mathbb R^3$ cannot be made into a real division algebra (and that extending complex multiplication would not work)
Prove that there are two frogs in one square.
Adjoint functors as “conceptual inverses”
Inverse Fourier transform of Gaussian
A twice continuously differentiable function
$\int\frac{dx}{x-3y}$ when $y(x-y)^2=x$?
Why does integrating a complex exponential give the delta function?
Frequency Swept sine wave — chirp

I’ve been getting the characteristic equation from relations of the form

$$U_n=3U_{n-1}-U_{n-3}$$

Thanks to this question I made before: How to get the characteristic equation?

- The disease problem
- Prove that if m and n are positive integers, and x is a real number, then: ceiling((ceiling(x)+n)/m) = ceiling((x+n)/m)
- Using generating functions find the sum $1^3 + 2^3 + 3^3 +\dotsb+ n^3$
- Can a collection of points be recovered from its multiset of distances?
- $\sum_{i=1}^n i\cdot i! = (n+1)!-1$ By Induction
- Function mapping challange

Now, I recently have been asked to get such equation from this:

$$f(n) = \begin{cases}5 & \text{ if n = 0} \\ f(n-1) + 3 + 2n + 2^n \end{cases}$$

I tried to apply the same idea. I took:

$$F_n=F_{n-1} + 3 + 2n + 2^n$$

Changed the subscripts to exponents…

$$F^n=F^{n-1} + 3 + 2n + 2^n$$

Replaced $F$ by the desired variable…

$$x^n=x^{n-1} + 3 + 2n + 2^n$$

Divided by the smallest exponent (I guess it is $n-1$):

$$x=1+ 3^{-x+1} + 2n^{-x+1} + 2^{n-x+1}$$

And this doesn’t look right. As you can see, the terms $3$, $2n$ and $2^n$ messed up the whole thing.

What did I do wrong, and how can I get the characteristic equation from this?

- Find the distance between two lines
- Linear algebra: Dimension and direct sum
- Prove that matrix is symmetric and positive definite given the fact that $A+iB$ is.
- Matrices whose Linear Combinations are All Singular
- Prove that the product of two positive semidefinite and symmetric matrices has non-negative eigenvalues
- Do $T$-invariant subspaces necessarily have a $T$-invariant complement?
- Not divisible by $2,3$ or $5$ but divisible by $7$
- Tensors in the context of engineering mechanics: can they be explained in an intuitive way?
- Show that there exists a $3 × 3$ invertible matrix $M$ with entries in $\mathbb{Z}/2\mathbb{Z}$ such that $M^7 = I_3$.
- Closedness of sets under linear transformation

Use the machinery of generating functions. Define $F(z) = \sum_{n \ge 0} f(n) z^n$, and write your recurrence as:

$$

f(n + 1) = f(n) + 5 + 2 n + 2^{n + 1}

$$

Multiply the recurrence by $z^n$, sum over $n \ge 0$ and recognize:

\begin{align}

\sum_{n \ge 0} f(n + 1) z^n &= \frac{F(z) – f(0)}{z} \\

\sum_{n \ge 0} z^n &= \frac{1}{1 – z} \\

\sum_{n \ge 0} n z^n

&= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 – z} \\

&= \frac{z}{(1 – z)^2} \\

\sum_{n \ge 0} 2^n z^n

&= \frac{1}{1 – 2 z}

\end{align}

Pulling all together:

$$

\frac{F(z) – 5}{z}

= F(z) + \frac{5}{1 – z} + \frac{2 z}{(1 – z)^2} + \frac{2}{1 – 2 z}

$$

Solving for $F(z)$, as partial fractions:

$$

F(z) = \frac{5 – 13 z + 8 z^2 – 2 z^3}{1 – 5 z + 9 z^2 – 7 z^3 + 2 z^4}

= \frac{2}{1 – 2 z} + \frac{1}{(1 – z)^2} + \frac{2}{(1 – z)^3}

$$

Using the (generalized) binomial theorem:

\begin{align}

f(n) &= 2 \cdot 2^n + \binom{-2}{n} (-1)^n + 2 \cdot \binom{-3}{n} (-1)^n \\

&= 2^{n + 2} + \binom{n + 2 – 1}{1} + 2 \cdot \binom{n + 3 – 1}{2} \\

&= 2^{n + 1} + n + 1 + \frac{(n + 2) (n + 1)}{2} \\

&= 2^{n + 1} + \frac{n^2 + 5 n + 4}{2}

\end{align}

Maxima’s help with the algebra is gratefully acknowledged.

The characteristic equation gets you solutions of a homogeneous equation,

in this case $f(n) = f(n+1)$ (but that’s too trivial, those solutions are constant). You then have to add particular solutions of the non-homogeneous equation. In this case look for a polynomial of degree $2$ solving $f(n) = f(n+1) + 3 + 2n$ and $2^n c$ solving $f(n) = f(n+1) + 2^n$.

- measurability of a function -equivalent conditions
- Is closure of convex subset of $X$ is again a convex subset of $X$?
- Why are all nonzero eigenvalues of the skew-symmetric matrices pure imaginary?
- What is the origin of the expression “Yoneda Lemma”?
- How to place objects equidistantly on an Archimedean spiral?
- Bruns-Herzog problem 3.1.25
- Prove that $A \subset B$ if and only if $A \cap B = A$
- Direct product and normal subgroup
- What is the asymptotic behavior of a linear recurrence relation (equiv: rational g.f.)?
- Is my proof of the additivity property of Riemann integral correct?
- Can we distinguish $\aleph_0$ from $\aleph_1$ in Nature?
- Separability and tensor product of fields
- Baire: Show that $f\colon \mathbb{R}\to\mathbb{R}$ is a polynomial in an open bounded set
- Splitting of prime ideals in algebraic extensions
- Does zero distributional derivative imply constant function?