Results 1 to 14 of 14

Math Help - Induction help needed

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    8

    Induction help needed

    I have two problems I need help with.

    1. Prove by induction that (7^(2n) - 48n - 1) modulus 2304 = 0.

    Right now I am stuck on the inductive step. I have this:

    (7^(2(k + 1)) - 48(k + 1) - 1) modulus 2304 = 0, equals
    (7^((2k + 2)) - 48k - 48 - 1) modulus 2304 = 0, equals
    (7^((2k + 2)) - 48k - 49) modulus 2304 = 0

    I don't know how to simplify the exponent on the 7, and don't know where to go from here.

    2. Sum (from i = 1 to n) of 1/(i^2)) <= (2 - 1/n)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2008
    From
    Scotland
    Posts
    901
    Quote Originally Posted by AlexH View Post
    I have two problems I need help with.

    1. Prove by induction that (7^(2n) - 48n - 1) modulus 2304 = 0.

    Right now I am stuck on the inductive step. I have this:

    (7^(2(k + 1)) - 48(k + 1) - 1) modulus 2304 = 0, equals
    (7^((2k + 2)) - 48k - 48 - 1) modulus 2304 = 0, equals
    (7^((2k + 2)) - 48k - 49) modulus 2304 = 0

    I don't know how to simplify the exponent on the 7, and don't know where to go from here.

    2. Sum (from i = 1 to n) of 1/(i^2)) <= (2 - 1/n)
    (7^{2n} - 48n - 1) \mod 2304 = 0 if  2304|(7^{2n} - 48n - 1)

    In other words,  (7^{2n} - 48n - 1) = 2304r
    For n = 1

    (7^{2} - 48 - 1) = 0 Hence true for n = 1.

    Assume true for n = k

     (7^{2k} - 48k - 1) = 2304r

    For n = k+1

      = (7^{2(k+1)} - 48(k+1) - 1)

     =  (7^{2k+2} - 48k-48 - 1)

     =  (7^{2k} \times 7^2 - 48k-49)

     =  (49\times7^{2k} - 48k-49)

     = 49(7^{2k} - 48k - 1) + 2304k

    You know that the left term is divisible by 2304, since that's what we assumed in the n=k step. And you know that the right term is divisible by 2304 because... well... it's pretty obvious!
    Last edited by Mush; February 2nd 2009 at 05:29 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Dec 2008
    From
    Scotland
    Posts
    901
    Quote Originally Posted by AlexH View Post
    2. Sum (from i = 1 to n) of 1/(i^2)) <= (2 - 1/n)
     \displaystyle \sum_{i=1}^{n} \frac{1}{i^2} \leq \bigg(2-\frac{1}{n}\bigg)

    Test for n = 1

     \displaystyle \sum_{i=1}^{1} \frac{1}{i^2} = \frac{1}{1^2}=1

    AND

    \bigg(2-\frac{1}{1}\bigg) = 1 So holds!

    Assume true for n = k


     \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} =  \leq \bigg(2-\frac{1}{n}\bigg)

    Or...

      \frac{1}{1^2} +\frac{1}{2^2}+\frac{1}{3^2}+...+\frac{1}{k^2}  =  \leq \bigg(2-\frac{1}{k}\bigg)

    For n = k + 1

     \displaystyle \sum_{i=1}^{k+1} \frac{1}{i^2} =\frac{1}{1^2} +\frac{1}{2^2}+\frac{1}{3^2}+...+\frac{1}{k^2} +  \frac{1}{(k+1)^2}

     \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} +  \frac{1}{(k+1)^2}

    We're trying to proove that our entire epxression is \leq \bigg(2-\frac{1}{k+1}\bigg) . You already know from the inductive step that the first term in your expression is \leq \bigg(2-\frac{1}{k}\bigg) . Does this help?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2009
    Posts
    8
    Quote Originally Posted by Mush View Post
    We're trying to proove that our entire epxression is \leq \bigg(2-\frac{1}{k+1}\bigg) . You already know from the inductive step that the first term in your expression is \leq \bigg(2-\frac{1}{k}\bigg) . Does this help?
    That helps with doing the first step, but I have no clue where you're going with this last thing you said.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2009
    Posts
    8
    In the first problem, how do you go from modulus 2304 = 0, to


    2304|(7^{2n} - 48n - 1)<br />
?

    I don't know what the vertical bar character means. Also what does 2304r mean?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Dec 2008
    From
    Scotland
    Posts
    901
    Quote Originally Posted by AlexH View Post
    In the first problem, how do you go from modulus 2304 = 0, to


    2304|(7^{2n} - 48n - 1)<br />
?

    I don't know what the vertical bar character means. Also what does 2304r mean?
    a|b means that a divides b and leaves no remainder.

    When we write b \mod a  , then we are referring to the remainder that is left when b is divided by a.

    So to say that  b \mod a = 0 , then we are saying that when a divides into b, the remainder is zero.

    IF that is the case, then we can say that a divides b. a|b.

    This means that when you divide b by a, you get an integer.

     \frac{b}{a} = r . r is any integer.

    Hence  b = ar .

    This theory applies to your case only instead of b we have  7^{2n} - 48n - 1 , and  a = 2304
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Dec 2008
    From
    Scotland
    Posts
    901
    Quote Originally Posted by AlexH View Post
    That helps with doing the first step, but I have no clue where you're going with this last thing you said.
    Okay, we KNOW that  \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} \leq \bigg(2 - \frac{1}{k}\bigg)

    But we are now dealing with the expression  \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} , and we're trying to prove that  \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} \leq \bigg(2 - \frac{1}{k+1}\bigg)

    I suggest we start with the first expression:

     \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} \leq \bigg(2 - \frac{1}{k}\bigg)

    Add \frac{1}{(k+1)^2} to both sides:

     \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2}  \leq \bigg(2 - \frac{1}{k}\bigg)+\frac{1}{(k+1)^2}

     \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} \leq \bigg(2 - \frac{(k+1)^2}{k(k+1)^2}+\frac{k}{k(k+1)^2}\bigg)

     \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} \leq \bigg(2 + \frac{k-(k+1)^2}{k(k+1)^2}\bigg)


     \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} \leq \bigg(2 - \frac{(k+1)^2-k}{k(k+1)^2}\bigg)


     \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} \leq \bigg(2 - \frac{k^2+2k+1-k}{k(k+1)^2}\bigg)

     \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} \leq \bigg(2 - \frac{k^2+k+1}{k(k+1)^2}\bigg)

     \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} \leq \bigg(2 - \frac{k^2+k}{k(k+1)^2} + \frac{1}{k(k+1)^2}\bigg)

     \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} \leq \bigg(2 - \frac{k(k+1)}{k(k+1)^2} + \frac{1}{k(k+1)^2}\bigg)

     \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} \leq \bigg(2 - \frac{1}{k+1} + \frac{1}{k(k+1)^2}\bigg)

    And clearly, if our last statement is true, then the statement

     \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} \leq \bigg(2 - \frac{1}{k+1}\bigg)

    Is true. And our LHS is the same as  \displaystyle \sum_{i=1}^{k+1} \frac{1}{i^2} , hence:

     \displaystyle \sum_{i=1}^{k+1} \frac{1}{i^2} \leq \bigg(2 - \frac{1}{k+1}\bigg)

    Solved.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jan 2009
    Posts
    8
    Quote Originally Posted by Mush View Post
     =  (49\times7^{2k} - 48k-49)

     = 49(7^{2k} - 48k - 1) + 2304k

    You know that the left term is divisible by 2304, since that's what we assumed in the n=k step. And you know that the right term is divisible by 2304 because... well... it's pretty obvious!
    Wait, how can you factor 49 out of -48k? The way I learned to factor things out, you have to factor it out of everything in in expression. I don't get what you're doing.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Dec 2008
    From
    Scotland
    Posts
    901
    Quote Originally Posted by AlexH View Post
    Wait, how can you factor 49 out of -48k? The way I learned to factor things out, you have to factor it out of everything in in expression. I don't get what you're doing.
    Okay.

    When you are carrying out these algebraic manipulations, you should always bear in the mind the result you got for n = k.

    For n = k, you got  7^{2k}-48k-1 = 2304r .

    For the case where n = k+1, your start-off expression is:

     7^{2k+1}-48(k+1)-1

    When we algebraically manipulate this, we always want to derive from it, the result we got when n = k. We have all the information we need to know about n = k, so if we can derive that case from the n = k+1 case, then we can deductively reason some results about n = k+1.

    So, you got to the stage where you had:

     49 \times 7^{2k} - 48k - 49

    Now, as I'm sure you appreciate, this expression is REMARKABLY close to the n = k expression. The only annoying thing, as you pointed out, is that 49 can't be factored out of -48k whilst it can be factored out of the other terms. But if you remember that our AIM is to end up with an expression that has the n=k expression embedded within it, then it should be fairly obviously that our expression MUST take the form:

     49(7^{2k} - 48k-1) + xk

    The xk outside the bracket is there to account for the fact that  49 \times (-48k) will give us an expression that is not equal to the one we started with.

    So!


     49(7^{2k} - 48k-1) + xk = 49 \times 7^{2k} - 48k - 49

    Expand the RHS

     49 \times 7^{2k} - 2352k-49 + xk = 49 \times 7^{2k} - 48k - 49


     - 2352k + xk =  - 48k

      xk =  - 48k+2352k

      xk =  2304k

    Hence

      49 \times 7^{2k} - 48k - 49=49(7^{2k} - 48k-1) + 2304k

    Does that make more sense?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jan 2009
    Posts
    8

    Post

    Nevermind, stupid question.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Jan 2009
    Posts
    8
    What do you do for a living where you are so good at math? I'm a computer science student (4th year). We have to take up to calculus 3 (3 dimensional calculus). I used to be so good at math but I haven't taken a class in it in 3 years. Most CS people don't need to know more than basic algebra anyway. All of this discrete math you don't even need to really know to be a good computer programmer. I love programming but this theoretical bullshit makes me want to kill someone.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Dec 2008
    From
    Scotland
    Posts
    901
    Quote Originally Posted by AlexH View Post
    What do you do for a living where you are so good at math? I'm a computer science student (4th year). We have to take up to calculus 3 (3 dimensional calculus). I used to be so good at math but I haven't taken a class in it in 3 years. Most CS people don't need to know more than basic algebra anyway. All of this discrete math you don't even need to really know to be a good computer programmer. I love programming but this theoretical bullshit makes me want to kill someone.
    Hi AlexH.

    I'm only a 2nd year Aeronautical Engineering student at Glasgow University in Scotland.

    Aeronautical Engineering is basically rocket science, and whilst the mathematics there is complex, I also supplement my learning with pure mathematics.

    I must say I disagree with you when you say that discrete mathematics isn't useful in 'real' programming. The more advanced and useful applications of computing science are highly dependent on advanced mathematics, and in some cases, even unconventional forms of mathematics.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Jan 2009
    Posts
    8
    Quote Originally Posted by Mush View Post
    Hi AlexH.

    I'm only a 2nd year Aeronautical Engineering student at Glasgow University in Scotland.

    Aeronautical Engineering is basically rocket science, and whilst the mathematics there is complex, I also supplement my learning with pure mathematics.

    I must say I disagree with you when you say that discrete mathematics isn't useful in 'real' programming. The more advanced and useful applications of computing science are highly dependent on advanced mathematics, and in some cases, even unconventional forms of mathematics.
    So you're going to be a real rocket scientist. That's great! I'm sure you'll find a good job with a defense contractor or something along those lines.

    I'm not saying that math isn't useful in computer programming. What I am saying is that the vast majority of computer programmers don't use it. Most programmers work in business applications. I'm sure that for scientific applications, an understanding of complex math is essential. Discrete math is very intuitive when you are working on a program. In my opinion it becomes harder to understand when it is abstracted and theorized like in this course. What I meant by "good programmer", is to have a good understanding of data structures, program design, and algorithms. For example, right now (for my Artificial Intelligence class) I am working on a basic neural network, in which choosing the right data structures can make your job much easier. Choices like that separate the average and above-average.

    What do you mean by unconventional mathematics?

    Thanks again for your help.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Dec 2008
    From
    Scotland
    Posts
    901
    Quote Originally Posted by AlexH View Post
    So you're going to be a real rocket scientist. That's great! I'm sure you'll find a good job with a defense contractor or something along those lines.

    I'm not saying that math isn't useful in computer programming. What I am saying is that the vast majority of computer programmers don't use it. Most programmers work in business applications. I'm sure that for scientific applications, an understanding of complex math is essential. Discrete math is very intuitive when you are working on a program. In my opinion it becomes harder to understand when it is abstracted and theorized like in this course. What I meant by "good programmer", is to have a good understanding of data structures, program design, and algorithms. For example, right now (for my Artificial Intelligence class) I am working on a basic neural network, in which choosing the right data structures can make your job much easier. Choices like that separate the average and above-average.

    What do you mean by unconventional mathematics?

    Thanks again for your help.
    Well I don't know if I'll actually go into the field of Aeronautical Engineering after I graduate, but I'll certainly have a first class degree in it! I'm not really into the whole 'defense' side of aviation either. A bit too unethical for my liking.

    I agree that a lot of the theoretical stuff you learn in university will never be used in industry. But it is a good basis for anything, really.

    By unconventional mathematics, I just mean mathematics that isn't normally used in your field. For example, I am not taught number theory in my course because it isn't conventionally utilised in Aeronautical Engineering. But sometimes, an innovator can take something that is never used in their field, and use it. Often is the case that this application of unconventional theory can lead to a revolution in the field. For example, the mathematics used in classical material science could never have led us to the nano-technology we take for granted now. It has truly revolutionised technology and material science, and it could never have been done with an innovation outside the norm.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Help needed for induction proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 5th 2011, 07:53 AM
  2. Induction help needed please
    Posted in the Differential Geometry Forum
    Replies: 9
    Last Post: January 19th 2010, 08:45 PM
  3. Replies: 2
    Last Post: December 4th 2008, 01:51 AM
  4. A proof with induction, really needed!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 5th 2008, 10:34 AM
  5. Physics help needed about magnetic induction
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: May 23rd 2007, 05:48 AM

Search Tags


/mathhelpforum @mathhelpforum