1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Determine closed expression

  1. Apr 10, 2012 #1
    determine a closed expression for b(n), given
    b(0) = 3
    b(n+1) = 2+[itex]\prod[/itex] (k=0 to n) * b(k) , n >= 0 , without using recursion og or the product given by [itex]\prod[/itex].


    I wanna start out by b(n+1) -1 = (b(n)-1)^2 for n >= 0 , but im not sure.

    kind regards
    Maxmilian
     
  2. jcsd
  3. Apr 10, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    What does the word "wanna" mean?

    Have you tried writing out the first few b(k), to see if there is any discernible pattern?

    RGV
     
  4. Apr 10, 2012 #3
    oh sry, wanna is my street slang for "want to".
    And no I havent
     
  5. Apr 10, 2012 #4

    Curious3141

    User Avatar
    Homework Helper

    The usual way to tackle this sort of problem is to write out the first few terms of the sequence, discern the pattern, then prove it by induction.

    Hint: think in terms of powers of 2 plus a little something.
     
  6. Apr 10, 2012 #5
    Thx for your reply.
    so for n = 1 , im getting ;

    2 + b(0) *b(1) = 2 + 3 * b(1)

    for n = 2 ;

    2 + 3 * b(1) * b(2)

    edit: could 2+3*b(n)! be a solution to the pattern ?

    Can anyone give me a hint for what I should do next ?
     
    Last edited: Apr 10, 2012
  7. Apr 10, 2012 #6
    any help is still appreciated
     
  8. Apr 10, 2012 #7

    Curious3141

    User Avatar
    Homework Helper

    No.

    b(n+1) = 2 + ∏(k from 0 to n) b(k)

    So b(1) = 2 + ∏(k from 0 to 0)b(k) = 2 + b(0) = 2 + 3 = 5.

    Can you now work out b(2), b(3), b(4) and b(5)? Try and see the pattern, then I (or someone else) can guide you through the induction if you still have problems.
     
  9. Apr 10, 2012 #8
    then
    b(2) = 2 + ∏(k from 0 to 1)b(k) = 2 + b(0)*b(1) = 2 + 3*b(1)

    b(3) = 2 + ∏(k from 0 to 2)b(k) = 2 + b(0)*b(1)*b(2) = 2 + 3*b(1)*b(2)

    b(4) = 2 + ∏(k from 0 to 3)b(k) = 2 + b(0)*b(1)*b(2)*b(3) = 2 + 3*b(1)*b(2)*b(3)

    b(5) = 2 + ∏(k from 0 to 4)b(k) = 2 + b(0)*b(1)*b(2)*b(3)*b(4) = 2 + 3*b(1)*b(2)*b(3)*b(4)

    right ?
     
  10. Apr 10, 2012 #9

    Curious3141

    User Avatar
    Homework Helper

    Yes, but calculate them (get the final numbers).

    You should be able to make out the pattern clearly by b(4). b(5) is a little large, so you may not want to bother with that.
     
  11. Apr 10, 2012 #10
    right.

    b(2) = 17
    b(3) = 257
    b(4) = 65537

    as far as a pattern goes for b(n) , I think I have a good idea (Fermet)
     
    Last edited: Apr 10, 2012
  12. Apr 10, 2012 #11

    Curious3141

    User Avatar
    Homework Helper

    Yes, they are Fermat numbers. Now prove it by induction.
     
  13. Apr 10, 2012 #12
    is recursion not a part of induction ?

    I might have misunderstood the "determine the closed expression - without using recursion" wrong. but if I wanted to prove it by induction. I would;

    1. prove the basis ;

    b(0)=2^(2^0) +1 = 3 , true , basis proven.

    2. prove inductionstep

    b(n) -> b(n+1)
    b(n) = 2^(2^n) +1 -> b(n+1)=2^(2^n+1) +1
    b(1) = 2^(2^1) +1 = 5 -> b(1+1)2^(2^1+1)+1 = 17

    both n and n+1 is true, so I have proven it for both n and n+1 - right ?
     
    Last edited: Apr 10, 2012
  14. Apr 10, 2012 #13

    Curious3141

    User Avatar
    Homework Helper

    What I mean is that you need to prove the closed form expression by mathematical induction. You've only inferred a pattern by observation, but you haven't rigorously proven it.

    Of course, you need to use the recursive relation in your proof. But it needs to be a formal inductive proof, starting with an inductive hypothesis.
     
  15. Apr 10, 2012 #14

    Curious3141

    User Avatar
    Homework Helper

    Let P(n) be the proposition that b(n) = 2^(2^n) + 1. This is the inductive hypothesis which you start by assuming.

    From this, you need to establish that P(n+1) is true, i.e. that b(n+1) = 2^(2^(n+1)) + 1.

    This needs to be an algebraic (symbolic) proof. Just verifying it for certain numerical n's is not sufficient.
     
  16. Apr 10, 2012 #15
    right.
    so I start with my hypothesis, then prove basis , then assume P(n) is true , then last prove P(n+1) is true. How do I prove P(n+1) is true?
     
  17. Apr 11, 2012 #16

    Curious3141

    User Avatar
    Homework Helper

    Wanted to reply to this earlier, but a lot of things came up.

    So assume P(n) is true. Hence you can write down b(n) = 2^(2^n) + 1

    Now you have to use this given relation: b(n+1) = 2 + ∏(from 0 to n) b(k)

    to somehow arrive at b(n+1) = 2^(2^(n+1)) + 1

    which would establish P(n+1).

    Here's a hint:

    ∏(from 0 to n) b(k) = b(n) * ∏(from 0 to (n-1)) b(k)

    and

    b(n) = 2 + ∏(from 0 to (n-1)) b(k),

    so ∏(from 0 to (n-1)) b(k) = b(n) - 2

    Can you put all that together and do the remaining algebra to prove the result?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook