1. ## recursion

how would you express recursively this functions and maps:

f(n) =∑ ceiling(i/2) for i=0 to n
f(n,k)= ∑ k+2i from i=0 to n
{0,1} f(x,y)={ 1 if x !=y; 0 otherwise}
f(x,y)={ 1 if x is a prefix of y; 0 otherwise}

thanks...

2. Hello ps1313
Originally Posted by ps1313
how would you express recursively this functions and maps:

f(n) =∑ ceiling(i/2) for i=0 to n
f(n,k)= ∑ k+2i from i=0 to n
{0,1} f(x,y)={ 1 if x !=y; 0 otherwise}
f(x,y)={ 1 if x is a prefix of y; 0 otherwise}

thanks...
Here's a solution to the first one.

$f(n) = f(n-2)+ \left\lceil\frac{n-1}{2}\right\rceil+\left\lceil\frac{n}{2}\right\rce il$

Now if $n$ is even:
$\left\lceil\frac{n}{2}\right\rceil = \frac{n}{2}$ and $\left\lceil\frac{n-1}{2}\right\rceil = \frac{n}{2}$

$\Rightarrow f(n) = f(n-2)+\frac{n}{2}+\frac{n}{2}$
$=f(n-2)+n$
And if $n$ is odd:
$\left\lceil\frac{n}{2}\right\rceil = \frac{n+1}{2}$ and $\left\lceil\frac{n-1}{2}\right\rceil = \frac{n-1}{2}$

$\Rightarrow f(n) = f(n-2)+\frac{n+1}{2}+\frac{n-1}{2}$
$=f(n-2) + n$
So for all $n$
$f(n) = f(n-2)+n$
$\Rightarrow f(n-2) = f(n-4) + (n-2)$

$\Rightarrow n = f(n-2) - f(n-4) + 2$

$\Rightarrow f(n) = f(n-2) +f(n-2) - f(n-4) + 2$

$\Rightarrow f(n)=2f(n-2)-f(n-4)+2$

3. thanks...

for the first one will it work the same way if its i/3 instead of i/2 can you do it for i/3 ???

4. Hello ps1313
Originally Posted by ps1313
thanks...

for the first one will it work the same way if its i/3 instead of i/2 can you do it for i/3 ???
No. Try a few values of $i$, and work out $\left\lceil\frac{i}{3}\right\rceil$:
$i = 0:\left\lceil\frac{i}{3}\right\rceil=0$

$i = 1:\left\lceil\frac{i}{3}\right\rceil=1$

$i = 2:\left\lceil\frac{i}{3}\right\rceil=1$

$i = 3:\left\lceil\frac{i}{3}\right\rceil=1$

$i = 4:\left\lceil\frac{i}{3}\right\rceil=2$

... and so on.
So instead of taking pairs of values of $n$, even and odd, you'll have to take groups of 3, depending on the remainder 0, 1 or 2, that $n$ leaves when divided by 3.

I haven't worked it out, but I suspect that you'll need to link $f(n)$ and $f(n-3)$ now, rather than $f(n)$ and $f(n-2)$. Try it and see.