Induction help needed

• Feb 2nd 2009, 03:27 PM
AlexH
Induction help needed
I have two problems I need help with.

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

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

$\displaystyle (7^(2(k + 1)) - 48(k + 1) - 1) modulus 2304 = 0, equals$
$\displaystyle (7^((2k + 2)) - 48k - 48 - 1) modulus 2304 = 0, equals$
$\displaystyle (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)
• Feb 2nd 2009, 04:03 PM
Mush
Quote:

Originally Posted by AlexH
I have two problems I need help with.

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

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

$\displaystyle (7^(2(k + 1)) - 48(k + 1) - 1) modulus 2304 = 0, equals$
$\displaystyle (7^((2k + 2)) - 48k - 48 - 1) modulus 2304 = 0, equals$
$\displaystyle (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)

$\displaystyle (7^{2n} - 48n - 1) \mod 2304 = 0$ if $\displaystyle 2304|(7^{2n} - 48n - 1)$

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

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

Assume true for n = k

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

For n = k+1

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

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

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

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

$\displaystyle = 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!
• Feb 2nd 2009, 04:06 PM
Mush
Quote:

Originally Posted by AlexH
2. Sum (from i = 1 to n) of 1/(i^2)) <= (2 - 1/n)

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

Test for n = 1

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

AND

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

Assume true for n = k

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

Or...

$\displaystyle \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 \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 \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2}$

We're trying to proove that our entire epxression is $\displaystyle \leq \bigg(2-\frac{1}{k+1}\bigg)$. You already know from the inductive step that the first term in your expression is $\displaystyle \leq \bigg(2-\frac{1}{k}\bigg)$. Does this help?
• Feb 2nd 2009, 04:46 PM
AlexH
Quote:

Originally Posted by Mush
We're trying to proove that our entire epxression is $\displaystyle \leq \bigg(2-\frac{1}{k+1}\bigg)$. You already know from the inductive step that the first term in your expression is $\displaystyle \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.
• Feb 2nd 2009, 04:50 PM
AlexH
In the first problem, how do you go from modulus 2304 = 0, to

$\displaystyle 2304|(7^{2n} - 48n - 1)$?

I don't know what the vertical bar character means. Also what does 2304r mean?
• Feb 2nd 2009, 05:42 PM
Mush
Quote:

Originally Posted by AlexH
In the first problem, how do you go from modulus 2304 = 0, to

$\displaystyle 2304|(7^{2n} - 48n - 1)$?

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 $\displaystyle b \mod a$, then we are referring to the remainder that is left when b is divided by a.

So to say that $\displaystyle 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.

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

Hence $\displaystyle b = ar$.

This theory applies to your case only instead of b we have $\displaystyle 7^{2n} - 48n - 1$, and $\displaystyle a = 2304$
• Feb 2nd 2009, 06:00 PM
Mush
Quote:

Originally Posted by AlexH
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 \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 \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2}$, and we're trying to prove that $\displaystyle \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 \displaystyle \sum_{i=1}^{k} \frac{1}{i^2} \leq \bigg(2 - \frac{1}{k}\bigg)$

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

$\displaystyle \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 \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 \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 \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 \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 \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 \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 \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 \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 \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 \displaystyle \sum_{i=1}^{k+1} \frac{1}{i^2}$, hence:

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

Solved.
• Feb 2nd 2009, 06:10 PM
AlexH
Quote:

Originally Posted by Mush
$\displaystyle = (49\times7^{2k} - 48k-49)$

$\displaystyle = 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.
• Feb 2nd 2009, 06:32 PM
Mush
Quote:

Originally Posted by AlexH
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 $\displaystyle 7^{2k}-48k-1 = 2304r$.

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

$\displaystyle 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:

$\displaystyle 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:

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

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

So!

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

Expand the RHS

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

$\displaystyle - 2352k + xk = - 48k$

$\displaystyle xk = - 48k+2352k$

$\displaystyle xk = 2304k$

Hence

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

Does that make more sense?
• Feb 2nd 2009, 06:40 PM
AlexH
Nevermind, stupid question.
• Feb 2nd 2009, 06:56 PM
AlexH
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.
• Feb 2nd 2009, 07:03 PM
Mush
Quote:

Originally Posted by AlexH
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.
• Feb 3rd 2009, 07:21 PM
AlexH
Quote:

Originally Posted by Mush
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. :)
• Feb 4th 2009, 03:49 AM
Mush
Quote:

Originally Posted by AlexH
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.