Results 1 to 3 of 3

Math Help - Mathematical induction

  1. #1
    Super Member
    Joined
    Jun 2008
    Posts
    829

    Mathematical induction

    Solve by induction.The recurrence

    S(n) = 1, for n=1
    S(n) = [S(\frac{n}{2})]+[S(\frac{n}{2})]+1, for n \geq 2
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,407
    Thanks
    1294
    Quote Originally Posted by Apprentice123 View Post
    Solve by induction.The recurrence


    S(n) = 1, for n=1

    S(n) = [S(\frac{n}{2})]+[S(\frac{n}{2})]+1, for n \geq 2
    That doesn't make a whole lot of sense...

    Is it possible to have \frac{3}{2} terms? Or any non-integer valued term? Because that's what you'd have for any odd n...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,685
    Thanks
    616
    Hello, Apprentice123!

    I believe you have misplaced the brackets . . .


    Solve by induction the recurrence:

    S(1) = 1
    S(n) \:=\:S\bigg(\!\!\left[\tfrac{n}{2}\right]\!\!\bigg) + S\bigg(\!\!\left[\tfrac{n}{2}\right]\!\!\bigg) +1 . for n \geq 2
    If I'm right, we have a fascinating "exponential" sequence . . .


    . . \begin{array}{ccc} \text{Group} & & \text{Value} \\ \hline S(1) &=& 1 \\ S(2),S(3) &=& 3 \\ S(4),S(5),S(6),S(7) &=& 7 \\ S(8),S(9),\;\hdots\; S(15) &=& 15 \\ S(16),S(17),\hdots S(31) &=& 31 \\ \vdots & & \vdots \end{array}


    Each group doubles in length.
    The n^{th} group has the value: . 2^n-1


    Good luck with the inductive proof . . .

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 31st 2010, 03:31 PM
  2. Mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 30th 2010, 05:54 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2009, 05:29 PM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 18th 2009, 08:35 AM

Search Tags


/mathhelpforum @mathhelpforum