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.

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

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

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

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

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

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

$\displaystyle \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 $\displaystyle i$, and work out $\displaystyle \left\lceil\frac{i}{3}\right\rceil$:
$\displaystyle i = 0:\left\lceil\frac{i}{3}\right\rceil=0$

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

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

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

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

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

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