Results 1 to 4 of 4

Thread: recursion

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    6

    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello ps1313
    Quote Originally Posted by ps1313 View Post
    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$
    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    6
    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 ???
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello ps1313
    Quote Originally Posted by ps1313 View Post
    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.

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recursion help.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 28th 2010, 02:23 PM
  2. Recursion Depth
    Posted in the Algebra Forum
    Replies: 0
    Last Post: Oct 27th 2009, 11:01 AM
  3. transfinite recursion
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Oct 25th 2009, 07:57 PM
  4. Recursion
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Sep 30th 2008, 09:40 PM
  5. Recursion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 16th 2008, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum