# Recurrence relation not working as expected

I was dealing with the following recursive formula which had three constants ($k_1, k_2, k_3$) where $x$ would always be an integer:

$$f(x) = \begin{cases} 0 & if x = 1\\ k_1f(x-1) + k_2x + k_3 & if x \ge 2\\ \end{cases}$$

I wanted to find an identity for this specific type of recursively defined function that could be expressed in terms of $x$.

The first thing I did was to operate the function for the purpose of dividing the problem into smaller parts and, by doing that, reduce the problem into a function. And so I did:

$$f(1) = 0\\ f(2) = 2k_2 + k_3\\ f(3) = k_1(2k_2 + k_3) + 3k_2 + k_3\\ f(4) = k_1^2(2k_2 + k_3)+ k_1(3k_2 + k_3) + 4k_2 + k_3\\ f(5) = k_1^3(2k_2 + k_3)+ k_1^2(3k_2 + k_3) + k_1(4k_2 + k_3) + 5k_2 + k_3\\ \vdots\\ f(x) = \sum_{i=1}^{x-1}k_1^{i-1}(ik_2 + k_3)$$

At that point, I wanted to find a way replace the summation for an algebratic expression with the same result. To do so, I assumed this identities were true.

My first step was to modify the formula for being able to apply the identities. Below it is shown most of the process and the simplification.

$$f(x) = \sum_{i=1}^{x-1}ik_2k_1^{i-1} + k_3k_1^{i-1}\\ f(x) = \sum_{i=1}^{x-1}ik_2k_1^{i-1} + \sum_{i=1}^{x-1}k_3k_1^{i-1}\\ f(x) = k_2(\sum_{i=1}^{x-1}ik_1^{i-1}) + k_3(\sum_{i=1}^{x-1}k_1^{i-1})\\ f(x) = k_2(\frac{\sum_{i=1}^{x-1}ik_1^i}{k_1}) + k_3(\frac{\sum_{i=1}^{x-1}k_1^i}{k_1})\\ f(x) = \frac{k_2}{k_1}(\frac{k_1 - xk_1^x + (x - 1)k_1^{x+1}}{(1 - k_1)^2}) + \frac{k_3}{k_1}(\frac{k_1 - k_1^x}{1 - k_1})\\ \vdots\\ f(x) = \frac{(k_1-1)k_1^xk_2x+((k_1-1)k_1^x-k_1^2+k_1)k_3+(k_1^{x+1}+k_1)k_2)}{(k_1^3-2k_1^2+k_1)}\\$$

The problem comes when I compute the result. My first issue is that when $k_1 = 0$ or $k_1 = 1$, which means that the denominator equals 0, because the formula is unuseful in this case. That means that, as it doesn't meet initial expectations, which were being able to compute any combination of $k_1$,$k_2$ and $k_3$ if they $\in \Bbb Z$, the function is wrong.

Apart from that, when I compute the result with any other combination of the constants, the result is not the same as the recursive fucntion result.

This is an example in which $k_1 = 2$, $k_2 = 2$ and $k_3 = 2$:

----------------------------------
| x  | Recursive | Non-recursive |
----------------------------------
| 1  | 0         | 8             |
| 2  | 6         | 20            |
| 3  | 20        | 48            |
| 4  | 50        | 112           |
| 5  | 112       | 256           |
| 6  | 238       | 576           |
| 7  | 492       | 1280          |
| 8  | 1002      | 2816          |
| 9  | 2024      | 6144          |
| 10 | 4070      | 13312         |
| 11 | 8164      | 28672         |
| 12 | 16354     | 61440         |
| 13 | 32736     | 131072        |
| 14 | 65502     | 278528        |
| 15 | 131036    | 589824        |
----------------------------------


To summarize, what I want to know is if I was wrong in some of the operations and whether there is an alternative to arrive to the formula I am looking for.

Thanks for your interest! I wold appreciate any contribution.

• Is $x$ integer? Jun 6 '13 at 21:38
• Yes. I've just edited the question. Jun 6 '13 at 21:42
• Your sum formula should be $$f(n)=\sum_{i=0}^{n-2}k_1^i((n-i)k_2+k_3),$$ and your nonrecursive formula should be $$f(n)=\frac{k_1^n (k_1 (k_2+k_3)-k_3)-k_1 (k_2 (n+1)+k_3)+k_2 n+k_3}{(k_1-1)^2}$$ (courtesy of Mathematica). Jun 6 '13 at 21:53
• Also, as you note, this expression fails when $k_1=1$, since this changes the form of the recurrence. Instead, you take the limit as $k_1\to1$ to get $f(n)=\frac n2(k_2(n+1)+2k_3)$ instead in this case. Jun 6 '13 at 21:58
• Oops, swap $n\mapsto n-1$ in the above two comments; I started my recurrence at $n=0$ instead of $n=1$. Jun 6 '13 at 23:05

This is an usual non-homogeneous recurrent equation.

First let us solve the homogeneous equation $$f(x) = k_1f(x-1).$$ Its general solution is $f_0(x) = Ck_1^x$. Next we find a particular solution of the non-homogeneous equation in the form $f_1(x)=ax+b$: $$ax+b = k_1[a(x-1)+b] + k_2x + k_3.$$ We get $a$ and $b$ from equations $a=k_1a+k_2, \ \ b=-k_1a+k_1b+k_3$. The general solution of the non-homogeneous equation is $f_0+f_1$. The constant $C$ will be found from the initial condition $f(1)=0$.

• +1 Short and simple while leaving some steps to the reader. Jun 6 '13 at 22:36
• I believe this is similar to my second approach, although I don't distinguish homogeneous vs. nonhomogeneous parts. Jun 6 '13 at 23:08
• @Code-Guru: Thank you. Jun 7 '13 at 6:33
• @Mario Carneiro: There is a general principle (similarly to differencial equations): general solution of the non-homogeneous equation (gsnhe)=gshe+psnhe. Jun 7 '13 at 7:15

Given $f(1)=0$ and $f(n)=k_1f(n-1)+k_2n+k_3$ for $n\in{\Bbb N}^{\ge2}$, we can note a sum form for $f(n)$: If I temporarily define $g(n)=k_1^{-n}f(n)$, we get the recurrence $$k_1^ng(n)=k_1^ng(n-1)+k_2n+k_3\implies g(n)=g(n-1)+k_1^{-n}(k_2n+k_3),$$

so $g(n)=\sum_{i=2}^n k_1^{-i}(k_2i+k_3)$ and $f(n)=\sum_{i=2}^n k_1^{n-i}(k_2i+k_3)$ (where the index starts at $2$ because the first nonzero term occurs for $f(2)$).

To make the sum above nonrecursive, we check our tables to see

\begin{align} \sum_{i=0}^{n-1} a^i&=\frac{1-a^n}{1-a} \\ \sum_{i=0}^{n-1}ia^i&=\frac{a-na^n+(n-1)a^{n+1}}{(1-a)^2}, \end{align}

so \begin{align}f(n)&=\sum_{i=2}^n k_1^{n-i}(k_2i+k_3) \\ &=\sum_{i=0}^{n-2} k_1^i(k_2(n-i)+k_3) \\ &=(k_2n+k_3)\sum_{i=0}^{n-2} k_1^i-k_2\sum_{i=0}^{n-2}ik_1^i \\ &=(k_2n+k_3)\frac{1-k_1^{n-1}}{1-k_1}-k_2\frac{k_1-(n-1)k_1^{n-1}+(n-2)k_1^n}{(1-k_1)^2} \\ &=\frac{-k_1^{n-1} (k_2+k_3)+k_1^n (2 k_2+k_3)-k_1 (k_2 n+k_2+k_3)+k_2 n+k_3}{(k_1-1)^2}, \end{align}

where the last expression is the output from Mathematica at the original recurrence.

Alternatively, knowing the form of the answer, we can actually just "guess the solution": the $n$ dependence of the answer is $f(n)=A\alpha^n+Bn+C$, and there are good reasons to guess this by looking at the original recurrence equation. Assuming this equation is correct, we can plug in to the recurrence:

$$f(1)=0=A\alpha+B+C$$ \begin{align}f(n)=A\alpha^n+Bn+C&=k_1(A\alpha^{n-1}+B(n-1)+C)+k_2n+k_3 \\ &=\frac{k_1A}\alpha\alpha^n+(k_1B+k_2)n+k_1(C-B)+k_3 \end{align}

Comparing these equations term-by-term, we see that $A=-\frac1\alpha(B+C)$, $k_1=\alpha$, $k_1B+k_2=B$, and $C=k_1(C-B)+k_3$ (four equations in four unknowns). Rewiting the solution in terms of just $B$ and $C$, we get $f(x)=B(n-k_1^{n-1})+C(1-k_1^{n-1})$, and the other two solve to find $$k_1B+k_2=B\implies B=\frac{k_2}{1-k_1}$$ and $$C=k_1\left(C-\frac{k_2}{1-k_1}\right)+k_3\implies C=\frac{k_3(1-k_1)-k_1k_2}{(1-k_1)^2},$$ so our final answer is

$$f(n)=(1-k_1^{n-1})\frac{k_3(1-k_1)-k_1k_2}{(1-k_1)^2}+(n-k_1^{n-1})\frac{k_2}{1-k_1},$$

which is also in agreement with our previous answer.

Edit: When $k_1=1$, the formula above does not work, because there is no longer an exponential growth; instead the recursion is $f(n)=f(n-1)+k_2n+k_3$, which is a sum of linear terms and hence quadratic. So our guess this time is $f(n)=Dn^2+Bn+C$, so that $f(1)=0=D+B+C$ and \begin{align} Dn^2+Bn+C=f(n-1)+k_2n+k_3&=D(n-1)^2+B(n-1)+C+k_2n+k_3 \\ &=Dn^2+(B-2D+k_2)n+(D-B+C+k_3), \\ \end{align}

whence $2D=k_2\implies D=\frac{k_2}2$ and $B=D-k_3=\frac{k_2}2-k_3$, and $D+B+C=0\implies$ $C=k_3-k_2$. Thus $$f(n)\Big|_{k_1=1}=\frac12(k_2n^2+(k_2-2k_3)n+2(k_3-k_2)).$$

An alternative way of getting this answer is to take the limit of the earlier expression for $f(n)$ as $k_1\to1$, which is arguably the easier route. Thus, although the original expression is defined for all $n,k_1,k_2,k_3\in{\Bbb R}$ with $k_1\ne1$, the singularity at $k_1=1$ is "removable" and can be repaired with this alternative definition for $k_1=1$ to make a function that is continuous on $(n,k_1,k_2,k_3)\in{\Bbb R}^4$.

• Thanks Mario! Very complete answer! Jun 7 '13 at 14:48
• However, do you think it is possible to find a formula that also works when $k_1 = 1$? Jun 7 '13 at 21:24
• @IOS_DEV I've edited my answer in response to your question. Jun 8 '13 at 4:04

As noted in the comments, the formula is $f(n) = \sum_{i=0}^{n-2}k_1^i((n-i)k_2+k_3)$.

This solves to

$\displaystyle\frac{k_1^n(2k_2+k_3)-k_1^{n-1}(k_2+k_3)-k_1(k_2(n+1)+k_3)+k_2n+k_3}{(k_1-1)^2}$

So for example, if $n= 10$ and $k_1 = k_2 = k_3 = 2$, we have

$2^{10}(2(2)+2) - 2^{9}(2+2)-2(2(11)+2)+2(10)+2 = 2^{10}(6)-2^{9}(4)-48+22$

$= 6144-2048 -26 = 4070$