Express $f(n+2)=f(n+1)+f(n)+(n+1)$, where $f(0)=0,f(1)=1$, as a Fibonacci Function

Question

I am currently solving a recursion problem.

If I have this function f(n+2)=f(n+1)+f(n)+(n+1) where f(0)=0,f(1)=1 It appears to me that this function can be reduced in form of fibonacci function.Can anyone tell me how this can be expressed as Fibonacci function.

The answer is f(n)=2(fib(n+2)-1)-n.

Can anyone explain how?

Answer 1

The Original Question

The equation that needs to be satisfied is $$ \left(S^2-S-1\right)f(n)=n+1 $$ where $Sf(n)=f(n+1)$ is the shift operator. $$ \begin{align} \left(S^2-S-1\right)(\color{#C00}{-2}\color{#090}{-n}\color{#00F}{+F_{n+3}}) &=\color{#C00}{2}\color{#090}{+n-1}\color{#00F}{+0}\\ &=n+1 \end{align} $$ Furthermore, $f(0)=-2+F_3=0$ and $f(1)=-3+F_4=0$.

Therefore, the solution to the original question, and the question in the title, is $$ \bbox[5px,border:2px solid #C0A000]{f(n)=F_{n+3}-n-2} $$

---

The Edited Question

The equation that needs to be satisfied is $$ \left(S^2-S-1\right)f(n)=n+2 $$ $$ \begin{align} \left(S^2-S-1\right)(\color{#C00}{-3}\color{#090}{-n}\color{#00F}{+2F_{n+1}+F_{n+2}}) &=\color{#C00}{3}\color{#090}{+n-1}\color{#00F}{+0}\\ &=n+2 \end{align} $$ Furthermore, $f(0)=-3+2F_1+F_2=0$ and $f(1)=-4+2F_2+F_3=0$.

Therefore, the solution to the edited question is $$ \bbox[5px,border:2px solid #C0A000]{f(n)=2F_{n+1}+F_{n+2}-n-3} $$

---

The Finally Edited Question

The equation that needs to be satisfied is $$ \left(S^2-S-1\right)f(n)=n+1 $$ $$ \begin{align} \left(S^2-S-1\right)(\color{#C00}{-2}\color{#090}{-n}\color{#00F}{+2F_{n+2}}) &=\color{#C00}{2}\color{#090}{+n-1}\color{#00F}{+0}\\ &=n+1 \end{align} $$ Furthermore, $f(0)=-2+2F_2=0$ and $f(1)=-3+2F_3=1$.

Therefore, the solution to the finally edited question is $$ \bbox[5px,border:2px solid #C0A000]{f(n)=2F_{n+2}-n-2} $$

Answer 2

Take $f_n=g_n+an+b$ where $g_n=g_{n-1}+g_{n-2}$ therefore:$$f_n=f_{n-1}+f_{n-2}+{n-1}\to g_n+an+b=g_{n-1}+an-a+b+g_{n-2}+an-2a+b+{n-1}$$so we get from here:$$a=-1,b=-2$$which leads us to$$f_n=g_n-n-2$$also $$g_n=Ar_1^n+Br_2^n$$ where $r_1$ and $r_2$ are roots of $r^2=r+1$ so we get from here:$$g_n=A\phi^n+B(1-\phi)^n$$where $\phi$ is Golden Ratio. Also $g_0=2$ and $g_1=3$ therefore:$$g_n=(1+\frac{{2}}{\sqrt 5})\phi^n+(1-\frac{{2}}{\sqrt 5})(1-\phi)^n$$and finally$$f_n=(1+\frac{{2}}{\sqrt 5})\phi^n+(1-\frac{{2}}{\sqrt 5})(1-\phi)^n-n-2$$

Answer 3

Add $a(n+2)+b$ on both sides, for some $a,b$ to be specified. You get, for all $n$, $$ f(n+2)+a(n+2)+b = f(n+1)+f(n)+n+2+a(n+2)+b $$ which, once simplified, gives $$ f(n+2)+a(n+2)+b = f(n+1)+f(n)+(a+1)n+2a+2+b\tag{1} $$ We want the RHS to look like $$ \left(f(n+1)+a(n+1)+b\right)+\left(f(n)+an+b\right) $$ i.e. to $$f(n+1)+f(n)+2an+a+2b\tag{2}$$

For (1) and (2) to be equal, we need $a+1=2a$ and $2a+2+b=a+2b$, i.e. $a=1$ and $b=3$. With this choice, we get, setting $$g(n)\stackrel{\rm def}{=} f(n)+n+3\tag{3},$$ that $$ g(n+2) = g(n+1)+g(n) $$ which is a Fibonacci sequence. Once you have $g$, you get $f$ by (3).