Find a recursive formula to the given closed formula

Question

I'm asked to find a recursive formula to this closed formula:

$$f(n) = 2n + 3^nn$$

I tried to transform this formula to a formula that I might get using the Characteristic polynomial method.

As I understand the $3^nn$ here implies that $x_{1}=x_{2}=3$ are solutions of the Characteristic polynomial but there should be $3^nn^0$ too. So I'm not sure how to solve this.

Answer 1

Nice problem, thank you.

First, find the ordinary generating function for the sequence $f(n).$ We have $$ \sum_{n >0}f(n)z^n=\sum_{n >0}(2\,n +n\, 3^n)z^n=2\sum_{n >0}n z^n+\sum_{n >0}n 3^n z^n=\\=2\,{\frac {z}{ \left( z-1 \right) ^{2}}}+3\,{\frac {z}{ \left( 3\,z-1 \right) ^{2}}}={\frac {z \left( 21\,{z}^{2}-18\,z+5 \right) }{ \left( 3\,z-1 \right) ^{2} \left( z-1 \right) ^{2}}}. $$ We see that the generating function is a rational function. It implies that $f(n)$ is a solution of a linear recurrence relation with constant coeficents of degree $4.$

The coeficients of the reccurence relation we find from the denominator of the generating function. We have $$ \left( 3\,z-1 \right) ^{2} \left( z-1 \right)^{2}=9\,{z}^{4}-24\,{z}^{3}+22\,{z}^{2}-8\,z+1 $$ These coefficients equal to the coefficients of the reccurence relation ( see for instance Stanley book Enumerative combinatorics): The sequence $$ a_n=\alpha_1 a_{n-1}+\alpha_2 a_{n-2}+\cdots+ \alpha_k a_{n-k}. $$ has a generating function with the denominator $$ 1-\alpha_1 z- \alpha_2 z^2 -\cdots- \alpha_k z^k, $$ and visa versa.

At last we get the reccurence relation $$ f(n)=8f(n-1)-22f(n-2)+24f(n-3)-9f(n-4),\\ f(0)=0, f(1)=5,f(2)=22,f(3)=87. $$

Answer 2

Let $X = \{ (u_0,u_1,u_2,\ldots) : u_i \in \mathbb{C} \}$ be the space of sequences indexed by $\mathbb{N}$, taking value in $\mathbb{C}$.
It is a vector space with respect to componentwise addition and multiplication.
Define a linear map $L : X \to X$ which shifts a sequence to the left. $$X \ni u = (u_0, u_1, \ldots ) \quad\mapsto\quad Lu = (u_1, u_2,\ldots ) \in X$$

In general, for any $\alpha \in \mathbb{C}$ and polynomial $p(x)$ of degree $d$, the sequence $p(n)\alpha^n$ will be a solution for the linear recurrence relation:

$$(L-\alpha)^{d+1}u = 0$$

Apply this to $f(n) = 2n + 3^n n$,

• the $2n$ term will get killed by $(L-1)^2$.
• the $3^n n$ term will get killed by $(L-3)^2$.

This implies the sequence $f(n)$ will be a solution for

$$\begin{align} (L-1)^2(L-3)^2 u = 0 \iff & (L^4-8L^3+22L^2-24L+9) u = 0\\ \iff & u_{n+4} - 8 u_{n+3} + 22u_{n+2} - 24 u_{n+1} + 9 u_n = 0 \end{align} $$

What's remain is to compute the first four values of $f(n)$ for a complete initial value problem of above recurrence relation.

Answer 3

Disclaimer: this is an elementary solution, I've never took discrete mathematics course. I got recurrence of only 3rd order, but it seems all right. However, it's possible this is not the method you're supposed to use.

Let's denote $$ x= 2n, \ y= 3^n n,\ z= 3^{n+1}. $$ (Those are linearly independent sequences of $n$, so we can't have fewer variables for linear equations.)

Write formulas for $f(n)$, $f(n+1)$, $f(n+2)$ using $x$, $y$, $z$: \begin{align} f(n)\phantom{+} &= x + y\\ f(n+1) &= x + 2 + 3y + z\\ f(n+2) &= x + 4 + 9y + 6z \end{align} Solve for $x$, $y$, $z$ and substitute this solution in formula for $f(n+3)$: $$ f(n+3) = x + 6 + 27y + 27 z $$

We get \begin{align} x &= \frac 1 4 (9f(n) -6 f(n+1)+f(n+2)+8)\\ y &= \frac 1 4 (-5f(n)+6 f(n+1)-f(n+2)-8)\\ z &= \frac 1 2 (3f(n)-4 f(n+1)+f(n+2)+4) \end{align} and finally $$ f(n+3) = 9f(n)-15 f(n+1)+7 f(n+2)+8 $$ or, perhaps more elegantly: $$ f(n) = 7 f(n-1)-15 f(n-2)+9f(n-3)+8. $$

Answer 4

Disclaimer: this is an elementary solution, I've never took discrete mathematics course.

This gives recurrence of only 2nd order, but more complex and with square root, so maybe of less practical use.

Let's denote $$ x= n, \ y= 3^n. $$

Write formulas for $f(n)$, $f(n+1)$, $f(n+2)$ using $x$ and $y$: \begin{align} f(n)\phantom{+} &= 2x + xy\\ f(n+1) &= 2x + 2 + 3xy + 3y\\ f(n+2) &= 2x + 4 + 9xy + 18y. \end{align} Manipulating first two equations, we get $$ f(n+1) - 3f(n) = -4x + 2 + 3y. $$ The system of this equation and the one for $f(n)$ can be easily solved for $x$ and $y$, it yields a quadratic equation (I'd recommend using shortcuts in process though, eg. $a=f(n)$, $b=f(n+1)$). Solve and substitute the solution in the formula for $f(n+2)$ (there are two solutions, but only one is positive). It will be easier to calculate, if we try to replace as much of the formula as possible with linear terms of $f(n)$ and $f(n+1)$ already. For example: $$ f(n+2) = 6f(n+1) - 9f(n) + 8x -8 \quad (= 6f(n+1) - 9f(n) + 8n -8). $$ The system of equations gives $$ x = \frac 1 8 \left(3f(n)-f(n+1)-4 + \sqrt{(3f(n)-f(n+1)-4)^2 + 48f(n)}\right) $$ and eventually $$ f(n+2) = 5f(n+1)-6f(n)-12 + \sqrt{(3f(n)-f(n+1)-4)^2 + 48f(n)}. $$