# Closed Form Recursive Functions

Find closed form of the following:

1.$C_n=C_{n-1}+2$ where $C_0=0$

2.$C_n=4C_{n-1}+6n-1$ where $C_0=2$

3.$C_n=C_{n-1}-C_{n-2}$ where $C_0=1,C_1=0$

1.

$C_n=C_{n-1}+2$

$C_{n-1}=C_{n-2}+2$

$C_{n-2}=C_{n-3}+2$

So $C_n=((C_{n-3}+2)+2)+2=C_{n-3}+2*3$ so for $n-k$ we get $$C_n=C_{n-k}+2k$$

when $n-k=0\iff n=k$ we get

$$C_n=0+2n=2n$$

Is it correct?

2.

$C_n=4C_{n-1}+6n-1$

$C_{n-1}=4C_{n-2}+6(n-1)-1$

$C_{n-2}=4C_{n-3}+6(n-2)-1$

So $$C_n=4(4(4C_{n-3}+6(n-2)-1)6(n-1)-1)+6n-1=\\=4^3*C_{n-3}+4^2*6(n-2)+2*6(n-1)+6n-4^2-4-1$$

And for $n-k$ we get

$$C_n=4^k*C_{n-k}+\sum_{i=0}^{k-1}4^i*6(n-i)-4^i=4^k*C_{n-k}+6\sum_{i=0}^{k-1}4^i((n-i)-1)$$

for $n-k=0\iff n=k$ we get

$$C_n=4^n*2+6\sum_{i=0}^{n-1}4^i((n-i)-1)$$

How should I continue?

3.

$C_n=C_{n-1}-C_{n-2}$

$C_{n-1}=C_{n-2}-C_{n-3}$

$C_{n-2}=C_{n-3}-C_{n-4}$

$C_{n-3}=C_{n-4}-C_{n-5}$

So $C_n=C_{n-4}-C_{n-5}-C_{n-4}-C_{n-3}-(C_{n-4}-C_{n-5}-C_{n-4})=-C_{n-3}$

How should I continue?

There is something with homogenous and finding complexity (Big O notnation)

• On (3), you don't need to go nearly as deep as you do: $C_n=C_{n-1}-C_{n-2}=(C_{n-2}-C_{n-3})-C_{n-2}=-C_{n-3}$. Jun 4, 2018 at 22:54
• On (3), just plug in the initial data and see what you get. You are given $C_0,C_1$ so you can compute $C_2$ and you've shown that once you know the value for $3$ consecutive integers, you know the value at all integers. Jun 4, 2018 at 22:59
• Can it be solve by linear recurrence relation? Jun 4, 2018 at 23:11

1. $C_n = 2n$, Your answer is correct

2. The proper equation is $C_n=4^n*2+\sum_{i=0}^{n-1}[4^i(6(n-i)-1)]$ not $\require{cancel} \cancel{C_n=4^n*2+6\sum_{i=0}^{n-1}4^i((n-i)-1)}$

$$\sum_{i=0}^{n-1}[4^i(6(n-i)-1)] = \sum_{i=0}^{n-1}[4^i(6(n-i))] - \sum_{i=0}^{n-1}[4^i]$$ $$= 6\sum_{i=0}^{n-1}[4^i(n-i)] - \sum_{i=0}^{n-1}[4^i]$$ Let's call the sums: $$= 6S_1 - S_2$$

To find $S_2$ you can simply use the geometric series formula or: $$S_2 = 1 + 4 +4^2+ ...+4^{n-1}$$ $$4S_2 = 4 +4^2+ ...+4^{n-1} + 4^n$$

$$3S_2 = 4^n - 1, S_2 = \frac{4^n -1}{3}$$

To find $S_1$: $$S_1 = n + 4(n-1) + 4^2(n-2) + 4^3(n-3) + ... + 4^{n-2}(2) + 4^{n-1}(1)$$ $$(\frac{1}{4})S_1 = \frac{n}{4} + (n-1) + 4(n-2) + 4^2(n-3) + ... +4^{n-2}(1)$$ $$(\frac{3}{4})S_1 = -\frac{n}{4} + 1 + 4 + 4^2 + ... + 4^{n-2} + 4^{n-1}$$ $$(\frac{3}{4})S_1 = 4^{n-1} -\frac{n}{4} + \frac{4^{n-1}}{3}$$ $$S_1 = \frac{4}{3} [4^{n-1} -\frac{n}{4} + \frac{4^{n-1}}{3}]$$ $$S_1 = [\frac{4^{n}}{3} -\frac{n}{3} + \frac{4^{n}-4}{9}]$$

$$6S_1 = 2(4^{n}) - 2n + \frac{2(4^{n}-4)}{3}$$ $$6S_1 - S_2 = 2(4^{n}) - 2n + \frac{2(4^{n}-4)}{3} - \frac{4^n -1}{3}$$ $$C_n = 2(4^n) + 2(4^{n}) - 2n + \frac{2(4^{n}-4)}{3} - \frac{4^n -1}{3}$$

$C_n = 4^{n+1} - \frac{4^{n}-1}{3} + \frac{2(4^n - 4)}{3} - 2n$

You can simplify however you want from there

1. notice that $$C_2 = -1,C_3 = -1,C_4 = -2,C_5 = -3, C_6 = -5 ...$$ This is exact same sequence as the Fibonacci sequence except that the terms are negative instead of positive.

Note that there is already a formula for the terms of the Fibonacci Sequence called Binet's Formula

"This formula provides the $n^{\text{th}}$ term in the Fibonacci sequence, and is defined using the recurrence formula:" $${\displaystyle F_0 =0\,}$$ $${\displaystyle F_1 =1\,}$$ $${\displaystyle F_n={\frac {(1+{\sqrt {5}})^{n}-(1-{\sqrt{5}})^{n}}{2^{n}{\sqrt{5}}}}}$$

Some adjustments to make: $C_n = -F(n+1)$

$$C_n = -\frac {(1+{\sqrt{5}})^{n+1}-(1-{\sqrt{5}})^{n+1}}{2^{n+1}{\sqrt{5}}}$$