1

I've solved this recurrence using the iteration method for even and odd values of $n$, but I cannot seem to find a singular explicit function that solves this recurrence for all values of $n$.

The recurrence is $$a(n) = \begin{cases} 1, & \text{if $n=0$} \\ 3^n-a(n-1)+1, & \text{otherwise} \end{cases}$$

Rohit Singh
  • 1,143
Ben Underwood
  • 11
  • 1
    See here how to format the math. Then read the comments, too. – dxiv May 28 '22 at 07:06
  • As a start, look at the generating function $G=\sum_{n=0}^{\infty}a_nx^n$ and compute $G+xG$. – C Squared May 28 '22 at 12:43
  • You know if you have found separate functions for even and odd say $f$ and $g$ respectively, you can always combine them as a single function given by $h(n) = \big(\frac{1 + (-1)^n}{2}\big) f(n) + \big(\frac{1 - (-1)^n}{2}\big) g(n) $, which holds for both even and odd n. – Anon May 28 '22 at 13:40

2 Answers2

3

Here is a way to solve it without particular/homogeneous solution. Note that $$(-1)^na_n-(-1)^{n-1}a_{n-1}=(-1)^n(3^n+1),$$ and telescope.

Bumblebee
  • 18,220
  • 5
  • 47
  • 87
  • 2
    @lhf It actually is telescoping, you dont simplify the signs in LHS i.e. $(-1)^4a_4 - (-1)^3a_3 = f(3) $, and $$(-1)^3a_3 - (-1)^2a_2 = f(2) $$, you add them up to get $(-1)^4a_4 - (-1)^2a_2 = f(3) + f(2)$, and you can do this till 1. – Anon May 28 '22 at 13:54
2

Let $A(x)=\sum_{n \ge 0} a_n x^n$ be the ordinary generating function. The recurrence and initial condition imply that \begin{align} A(x) &= a_0 x^0 + \sum_{n \ge 1} a_n x^n \\ &= 1 + \sum_{n \ge 1} (3^n - a_{n-1} + 1) x^n \\ &= 1 + \sum_{n \ge 1} (3x)^n - x \sum_{n \ge 1} a_{n-1} x^{n-1} + \sum_{n \ge 1} x^n \\ &= 1 + \frac{3x}{1-3x} - x A(x) + \frac{x}{1-x}, \end{align} so \begin{align} A(x) &= \frac{1 + \frac{3x}{1-3x} + \frac{x}{1-x}}{1+x} \\ &= \frac{1 - 3x^2}{(1-x)(1+x)(1-3x)} \\ &= \frac{1/2}{1-x} - \frac{1/4}{1+x} + \frac{3/4}{1-3x} \\ &= \frac{1}{2}\sum_{n\ge 0} x^n - \frac{1}{4}\sum_{n\ge 0} (-x)^n + \frac{3}{4}\sum_{n\ge 0} (3x)^n \\ &= \sum_{n\ge 0} \left(\frac{1}{2} - \frac{1}{4} (-1)^n + \frac{3}{4} 3^n\right)x^n, \end{align} which immediately yields $$a_n = \frac{2-(-1)^n+3^{n+1}}{4}.$$

RobPratt
  • 45,619