Closed Form Recursive Functions

Question

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)

Answer 1

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

---

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