# Thread: formula for recursive definition

1. ## formula for recursive definition

Hello,

What is the formula for the following recursive definition...

$f(0)=1, f(1)=0, f(2)=2, f(n)=2f(n-3), n>=3$

The sequence is 2, 0, 4, 4, 0, 8, 8, 0 ...

2. Originally Posted by robocop_911
Hello,

What is the formula for the following recursive definition...

$f(0)=1, f(1)=0, f(2)=2, f(n)=2f(n-3), n>=3$

The sequence is 2, 0, 4, 4, 0, 8, 8, 0 ...
Actually its a tricky way of combining three separate sequences.

Let $n = 3k$ and $f(3m) = a_m$ then:
$f(n)=2f(n-3), n \geq 3 \Rightarrow a_k = f(3k)=2f(3k-3) = 2f(3(k-1)) = 2a_{k-1}, k \geq 1$ with $a_0 = 1$

Now, for $n = 3k+1$ and $f(3m + 1) = b_m$ then:
$b_k = f(3k + 1)=2f(3k+1 - 3) = 2f(3(k-1) + 1) = 2b_{k-1}, k \geq 1$ with $b_0 = 0$

Finally $n = 3k+2$ and $f(3m + 2) = c_m$ then:
$c_k = f(3k + 2)=2f(3k+2 - 3) = 2f(3(k-1) + 2) = 2c_{k-1}, k \geq 1$with $c_0 = 2$

So $a_k = 2^k , b_k = 0, c_k = 2^{k+1}$

3. Originally Posted by Isomorphism
Actually its a tricky way of combining three separate sequences.

Let $n = 3k$ and $f(3m) = a_m$ then:
$f(n)=2f(n-3), n \geq 3 \Rightarrow a_k = f(3k)=2f(3k-3) = 2f(3(k-1)) = 2a_{k-1}, k \geq 1$ with $a_0 = 1$

Now, for $n = 3k+1$ and $f(3m + 1) = b_m$ then:
$b_k = f(3k + 1)=2f(3k+1 - 3) = 2f(3(k-1) + 1) = 2b_{k-1}, k \geq 1$ with $b_0 = 0$

Finally $n = 3k+2$ and $f(3m + 2) = c_m$ then:
$c_k = f(3k + 2)=2f(3k+2 - 3) = 2f(3(k-1) + 2) = 2c_{k-1}, k \geq 1$with $c_0 = 2$

So $a_k = 2^k , b_k = 0, c_k = 2^{k+1}$
Hi, I just need a simple formula what's all this?

I have to first figure out a sequence from the recursive definition e.g. here it is 1 0 2 2 0 4 4 0 8 8 0... then find a formula which gives such a sequence and then prove it using mathematical induction!