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.
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$.