1
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ 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}$. $\endgroup$ Jun 4, 2018 at 22:54
  • $\begingroup$ 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. $\endgroup$
    – saulspatz
    Jun 4, 2018 at 22:59
  • $\begingroup$ Can it be solve by linear recurrence relation? $\endgroup$
    – newhere
    Jun 4, 2018 at 23:11

1 Answer 1

1
$\begingroup$
  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}}} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.