Results 1 to 4 of 4

Math Help - 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.

    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
    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 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.

    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: March 28th 2010, 02:23 PM
  2. Recursion Depth
    Posted in the Algebra Forum
    Replies: 0
    Last Post: October 27th 2009, 11:01 AM
  3. transfinite recursion
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 25th 2009, 07:57 PM
  4. Recursion
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 30th 2008, 09:40 PM
  5. Recursion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 16th 2008, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum