How do I solve the non-homogeneous recurrence relation $f(n) = f(n-3) +1$?

Question

This is part of a question from my combinatorics homework I've been trying to solve for a few days now... The initial conditions are: f(0)=f(1)=f(2)=1 I tried first to solve the homogeneous part by guessing. My result is $f(n)= \lfloor \frac{n}{3} \rfloor$ but I need to show a formal calculation, and I'm not really sure how to do it. I'm also not sure how to use the solution to the homogeneous recurrence in order to find the solution to the non-homogeneous relation given.

Thank you in advance for your help.

Answer 1

Hints:

• solve characteristic equation $r^3=1$
• solutions are $f(n)=a1^n+bj^n+cj^{2n}$
• RHS$=1$ is a root so find a particular solution of degree +1, that is $\alpha n$

Answer 2

We have $$f(3)=f(0)+1$$ $$f(6)=f(3)+1=f(0)+2$$ and so by induction, $f(3n)=f(0)+n=n+1$

Similarly, $f(3n+1)=n+1$ and $f(3n+2)=n+1$

Now to unite the arguement, we can say that $$x \in \{3n,3n+1,3n+2\} \implies \left\lfloor \frac{x}{3} \right\rfloor = n$$ Thus, $f(x)=\left\lfloor \frac{x}{3} \right\rfloor + 1$ Hope that helps!

Answer 3

From your initial conditions, I think you meant $f(n)=\left\lfloor\frac n3\right\rfloor+1$.

---

A Difference Equation Approach

Using the shift operator on sequences $Sf(n)=f(n+1)$, we get $$ \begin{align} 1 &=\left(I-S^{-3}\right)f(n)\tag1\\ &=\left(I+S^{-1}+S^{-2}\right)(I-S^{-1})f(n)\tag2\\ &=\color{#00F}{\left(I-\omega^{-1}S^{-1}\right)}\color{#090}{\left(I-\omega S^{-1}\right)}\color{#C00}{\left(I-S^{-1}\right)}f(n)\tag3 \end{align} $$ $(1)$: original equation; $1=f(n)-f(n-3)$
$(2)$: this shows that $n\mapsto3$, so $f(n)=\frac13n$ is a solution
$(3)$: full factorization, with $\omega=e^{i2\pi/3}$, to get the homogeneous part

Therefore, using Linear Difference Equations, we get the general solution to be $$ \begin{align} f(n) &=\frac13n+\color{#C00}{c_1}+\color{#090}{c_2\omega^n}+\color{#00F}{c_3\omega^{-n}}\tag4\\ &=\frac13n+c_1+c_4\cos\left(\frac{2n\pi}{3}\right)+c_5\sin\left(\frac{2n\pi}{3}\right)\tag5 \end{align} $$ Now we just need to compute $c_1$, $c_4$, and $c_5$ from the initial conditions $f(0)=f(1)=f(2)=1$, which gives $$ f(n)=\frac13n+\frac23+\frac13\cos\left(\frac{2\pi n}3\right)+\frac1{3\sqrt3}\sin\left(\frac{2\pi n}3\right)\tag6 $$

Answer 4

Using the recursive relation, we get \begin{align} f(n) &= f\left(3\left\lfloor \frac{n}{3} \right\rfloor+n\bmod 3\right) \\ &= f\left(3\left[\left\lfloor \frac{n}{3} \right\rfloor-1\right]+n\bmod 3\right)+1 \\ &= f\left(3\left[\left\lfloor \frac{n}{3} \right\rfloor-2\right]+n\bmod 3\right)+2 \\ &\vdots\\ &=f\left(n\bmod 3\right) +\left\lfloor \frac{n}{3} \right\rfloor\\ &=\left\lfloor \frac{n}{3} \right\rfloor+1, \end{align} where we use the initial condition because $(n \bmod 3)\in\{0,1,2\}$.

Answer 5

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ With $\ds{\mrm{f}\pars{0} = \mrm{f}\pars{1} = \mrm{f}\pars{2} = 1}$: $$ \bbox[5px,#ffd]{\sum_{n = 3}^{\infty}\mrm{f}\pars{n}z^{n}} = \bbox[5px,#ffd]{\sum_{n = 3}^{\infty}\mrm{f}\pars{n - 3}z^{n} + \sum_{n = 3}^{\infty}z^{n}} $$ $$ \underbrace{-\mrm{f}\pars{0} - \mrm{f}\pars{1}z -\mrm{f}\pars{2}z^{2}} _{\ds{-1 - z - z^{2}}}\ +\ \underbrace{\overbrace{\sum_{n = 0}^{\infty}\mrm{f}\pars{n}z^{n}} ^{\ds{\equiv\ \mathcal{F}\pars{z}}}} _{\ds{\mrm{f}\pars{n} = \bracks{z^{n}}\mathcal{F}\pars{z}}} = z^{3}\sum_{n = 0}^{\infty}\mrm{f}\pars{n}z^{n} + {z^{3} \over 1 - z} $$

---

\begin{align} \mathcal{F}\pars{z} & = {1 \over \pars{1 - z}^{2}\pars{1 + z + z^{2}}} = {1 \over \pars{1 - z}\pars{1 - z^{3}}} = \sum_{i = 0}^{\infty}\sum_{j = 0}^{\infty}z^{i + 3j} \\[5mm] \mrm{f}\pars{n} & = \sum_{i = 0}^{\infty}\sum_{j = 0}^{\infty}\bracks{i + 3j = n} = \sum_{i = 0}^{\infty}\sum_{j = 0}^{\infty}\bracks{i = n - 3j} = \sum_{j = 0}^{\infty}\bracks{n - 3j \geq 0} \\[5mm] = &\ \sum_{j = 0}^{\infty}\bracks{j \leq {n \over 3}} = \sum_{j = 0}^{\left\lfloor\,{n/3}\,\right\rfloor}1 \implies\bbx{\mrm{f}\pars{n} = \left\lfloor\,{n \over 3}\,\right\rfloor + 1} \\ & \end{align}