Straight Dope Message Board > Main Help with my maths exam
 Register FAQ Calendar Mark Forums Read

#1
05-24-2004, 12:53 PM
 bryn2kay Guest Join Date: May 2004
Help with my maths exam

Hi, I am studying for a BSc in Computer Science, and on Wednesday I have an exam covering the mathematics module for this term. Problem is, I'm missing quite a few notes from this module. So I bought a few past exams from the University with an answer sheet, but unfortunately there is no working shown, so I can't see how certain answers are achieved.

I was hoping that if I posted some of the questions I'm having problems with here, some kind soul might be able to expand on how the answers are found? It would be a great help!

Ok, here goes:

Quote:
 A function f, of natural numbers n>= 0, is defined by setting f(0) = 3 and f(1) = 8, and by computing the other values of f(n) from the following recurrence relation: f(n + 1) = 5 f(n) - 6 f(n - 1). Give an explicit definition of f(n) in terms of n.
---------
Quote:
 Prove by mathematical induction that, for all natural numbers n >= 1, (-3) + 4 + ... + (n + 2)(2n - 3) = n(4n² + 9n - 31) / 6
---------

Quote:
 Use the binomial theorem to find the coefficient of x³ in the expansion of (1 - x)^5 (1 + 2x)^6.
---------

Quote:
 Using row-reduction, determine whether the following matrix has an invers, and, if it does, find it's inverse: 1 1 2 1 2 1 2 3 1
---------

Quote:
 (i) In the following simultabeous equations, the number k is not known, but it is known that when the row-reduction method is applied to the equations, they will have no solution. Find the value that k must have. x + y + 3z = 2, 5x + 6y + 10z = 9, 2x + y + kz = 9. (ii) Make k = 7 in the equations in (i), and solve the equations.

These are the main questions I have trouble with. The paper is photocopied so has the answers scribbled on, but no working shown (i.e it says the coefficient of x³ is -30 , but not how that was found. Could anyone possibly take a little time to explain how to answer one, or more of the questions (for row-reduction as an example, I know I start like this:

1 1 2 | 1 0 0
1 2 1 | 0 1 0
2 3 1 | 0 0 1

and the apply one of three actions to any row (swap 2 rows, multiply one row, or subtract one from another) in order to get the left hand side to appear as the right currently is. I must keep making the same mistake because I can never get it to display the inverse (which is in the answer sheet, so I know its there).

Any help greatfully accepted!

Thanks, Bryn.
#2
05-24-2004, 01:29 PM
 SimonMoon5 Guest Join Date: Mar 2002
Don't have time to do all of these, but the induction one is the simplest.

Step 1: prove it's true if n = 1.
Easy. On the left, you just have 1 term, -3. On the right, plug in n = 1, and the result is -3.

Step 2: Prove that if it's true for n, then it is also true for n+1.

So, you assume the equation is true as written for some value of n. Then, try using n+1. On the left side of the equation, you get an extra term which looks like (n+1 + 2)(2(n+1) - 3) which simplifies to 2n^2 - 5n - 3.

You want to show the new left side will equal the right side of the equation, with n+1 substituted for n. Do a little algebra, and the new right side of the equation is the same as the old right side of the equation with a few extra terms. Simplify, and these extra terms reduce to (12n^2 + 30 n - 18)/6.

Of course, you already know that the old right side equals the old left side, so you just need to show that the new terms on the left (2n^2 - 5n - 3) will equal the new terms on the right (12n^2 + 30 n - 18)/6. Cancel a 6, and you're done.
#3
05-24-2004, 01:31 PM
 SimonMoon5 Guest Join Date: Mar 2002
Oops. Of course, everywhere I wrote -5n, replace with +5n.
#4
05-24-2004, 01:32 PM
 Crafter_Man Member Join Date: Apr 1999 Location: Ohio Posts: 8,591
Quote:
 Originally Posted by bryn2kay I'm missing quite a few notes from this module
Sounds like we've found the problem.
#5
05-24-2004, 01:53 PM
 SimonMoon5 Guest Join Date: Mar 2002
Also, for the binomial theorem problem, well...

You should know that the binomial theorem tells you how to expand (a+b)^n. In fact, you can find the coefficent for any term that you want. For the problem you're given, though, you have two polynomials that you need to expand.

I'd say, first use the binomial theorem to find the first few terms of (1-x)^5. (You won't need more than the constant term, the x term, the x^2 term, and the x^3 term.) Then, do the same for (1 + 2x)^6. Now, that you've satisfied the "use the binomial theorem" requirement for this problem, use algebra to multiply out the product of these polynomials (or at least the constant through x^3 terms).

Then, you'll have a bunch of terms. Combine like terms. Find the x^3 term. Look at its coefficient. Write down the coefficient as the answer.
#6
05-24-2004, 02:14 PM
 bryn2kay Guest Join Date: May 2004
Thanks for the speedy response!

I must admit that I was thrown by the binomial question because all the questions I had tried before looked more like

Use the binomial theorem to find the coefficient of x³ in the expansion of
(1 - x)^5

so I was stuck on how I should answer the question on this paper as it had two parts. Your solution looks perfectly reasonable to me though - I guess I was staring at my notepad for too long hehe!

Yes, the main problem is missing notes (I write out the notes I take by hand and as such have no 'back-up copy'. I should really start typing them up/photocopying them - a portion of them were partially destroyed when my squash leaked in my bag )

So I have most of the methods in my head, but have lost many of the examples that we did in lecture, and I find it easier to learn from going through examples than just reading the basic theory.

Once again, many thanks for helping! I think induction is just one of those things that is very easy, but I'll have to practice a few questions before it sinks in. It amazes me how powerful a tool it is though
#7
05-24-2004, 02:18 PM
 SimonMoon5 Guest Join Date: Mar 2002
For the last problem with

x + y + 3z = 2,
5x + 6y + 10z = 9,
2x + y + kz = 9.

i.e.,

1 1 3 2
5 6 10 9
2 1 k 9

Simply take 5 times the first row and subtract it from the second row. That gives you:

x + y + 3z = 2
y - 5z = -1
2x + y + kz = 9

Or, in other words,

1 1 3 2
0 1 -5 -1
2 1 k 9

Now, do this sort of trick again. Take 2 times the first row and subtract it from the third row. That gives you

1 1 3 2
0 1 -5 -1
0 -1 (-6+k) 5

Then, add the second row to the third row. That gives you

1 1 3 2
0 1 -5 -1
0 0 (-11 + k) 4

So, that last row means the equation (-11 + k)z = 4. Clearly, if -11 + k = 0, there is no solution. So, k must not be 11, or else there will be no solution.

What if k = 7? Well, then it's easy. -4z = 4, so z = -1, and then you can easily find x and y.
#8
05-24-2004, 04:03 PM
 SimonMoon5 Guest Join Date: Mar 2002
Quote:
 I know I start like this: 1 1 2 | 1 0 0 1 2 1 | 0 1 0 2 3 1 | 0 0 1 and the apply one of three actions to any row (swap 2 rows, multiply one row, or subtract one from another) in order to get the left hand side to appear as the right currently is. I must keep making the same mistake because I can never get it to display the inverse (which is in the answer sheet, so I know its there).
First, get rid of the x's below the first row.

(1) Subtract the first row from the second row.

1 1 2 | 1 0 0
0 1 -1| -1 1 0
2 3 1 | 0 0 1

(2) Then, take twice the first row and subtract from the third row.

1 1 2 | 1 0 0
0 1 -1 | -1 1 0
0 1 -3 | -2 0 1

Now, you just need to get rid of the y below the second row. So, take the second row and subtract from it the third row.

1 1 2 | 1 0 0
0 1 -1 | -1 1 0
0 0 -2 | -1 -1 1

Now, multiply the third row by -1/2.

1 1 2 | 1 0 0
0 1 -1 | -1 1 0
0 0 1 | ½ ½ -½

Now, you're almost done. Get rid of the z's in the second row by adding the third row to the second row.

1 1 2 | 1 0 0
0 1 0 | -½ 1½ -½
0 0 1| ½ ½ -½

Now, get rid of the y and z in the first row. First, subtract the second row from the first row.

1 0 2 | 1½ -1½ ½
0 1 0 | -½ 1½ -½
0 0 1| ½ ½ -½

Then, subtract twice the third row from the first row.

1 0 0 | ½ -2½ 1½
0 1 0 | -½ 1½ -½
0 0 1| ½ ½ -½

How's that?

That means that the inverse matrix is
½ -2½ 1½
-½ 1½ -½
½ ½ -½
#9
05-24-2004, 04:56 PM
 dethtoll Guest Join Date: May 2004
As for the first one:

The general formula that should be your first 'guess' for second order linear recurrence problems [i.e F(n+1) = aF(n) + bF(n-1)] is c(p^n) + d(q^n)
To find p and q, you treat this as a binomial, so F(n+1) - 5F(n) + 6F(n-1) = 0.
The F(.)'s are treated as a variable, so we have z^2 - 5z + 6 = 0, giving 2 and 3 as solutions for the equation, which are p and q respectively in our original equation.

This brings our guess to F(n) = c(2^n) + d(3^n).
To find c and d, we plug in the given values, so F(0) = c + d = 3 and F(1) = 2c + 3d = 8
Solving these two equations gives c = 1 and d = 2.

Thus the final equation is: F(n) = (2^n) + 2(3^n), which satisfies the recurrence

The only time this trick doesn't work is when you find that p and q are the same. The general formula in this case is c(p^n) + d*n(q^n)
#10
05-24-2004, 05:23 PM
 MikeS Charter Member Join Date: Oct 2001 Location: Williamstown, MA Posts: 3,156
Quote:
 Originally Posted by bryn2kay A function f, of natural numbers n>= 0, is defined by setting f(0) = 3 and f(1) = 8, and by computing the other values of f(n) from the following recurrence relation: f(n + 1) = 5 f(n) - 6 f(n - 1). Give an explicit definition of f(n) in terms of n.
Problems like this are generally solved using generating functionals. Here's the basic idea:
1. Define an infinite polynomial G(x) in some variable x such that

G(x) = f(0) + f(1)x + f(2)x2 + f(3)x3 + ...

Don't worry about convergence, etc. of this polynomial; it's really just an infinite set of placeholders (as we'll see below.)
2. Rewrite the above recursion relation as

f(n+1) - 5 f(n) + 6 f(n-1) = 0
3. Now for the trick. Add the three equations below together:

G(x) = f(0) + f(1)x + f(2)x2 + f(3)x3 + ...
-5x G(x) = -5 f(0)x - 5 f(1)x2 - 5 f(2)x3 - 5 f(3)x4 + ...
6x2 G(x) = 6 f(0)x2 + 6 f(1)x3 + 6 f(2)x4 + 6 f(3)x5 + ...

If you stare at this for a bit, you'll see that when we add these together, all of the terms on the RHS that are second-order or higher in x cancel out because of the trick. For example, the total coefficient of x2 is f(2) - 5 f(1) + 6 f(0), which is zero because of the recursion relation. Adding the polynomials therefore gives us

G(x)(1 - 5x + 6x2) = f(0) + (f(1) - 5 f(0))x

Plugging in the values of f(0) = 3 and f(1) = 8 gives us the result that

G(x) = (3 - 7x)/(1 - 5x + 6x2) = (3 - 7x)/((1 - 3x)(1 - 2x))
4. If you know the power series coefficients for G(x) off the top of your head now, you're done. I can't figure them out off the top of my head, though, so I'll use partial fractions to figure them out. We write

G(x) = A/(1 - 3x) + B/(1 - 2x)

Putting everything on a common denominator yields

G(x) = ((A + B) - (2A + 3B)x)((1 - 3x)(1 - 2x))

Matching this with the polynomial we got above, this means that A + B = 3 and 2A + 3B = 7. The solution to this is A = 2, B = 1. So

G(x) = 2/(1 - 3x) + 1/(1 - 2x)

Now, I know that the power series for 1/(1 - nx) is 1 + nx + (nx)2 + (nx)3 + ... This means that

G(x) = 2(1 + 3x + 32x2 + ...) + (1 + 2x + 22x2 + ...)

and so, identifying coefficients, f(n) = 2*3n + 2n.

It may seem a little complicated the way I've described it here, but it's actually fairly straightforward once you get the hang of it. Try it with an arbitrary recursion relation to get a feel for it.

On preview, dethtoll seems to have beaten me to the punch with a nice quick algorithm for finding the solutions. Given that you're a CS major and not a discrete mathematician, his method is probably the only one you're expected to know. But now you know the whole sordid truth behind the formula.
#11
05-24-2004, 06:04 PM
 bryn2kay Guest Join Date: May 2004
My sincere thanks to everyone who has helped me tonight. You have definitely improved my understanding of these questions (well, in all honesy the first and third questions are still giving me problems - but that is due to my limited understanding, and not the excellent answers you've provided.

Again, thanks! You've made a dodgy student that little bit more confident lol
#12
05-24-2004, 06:14 PM
 nivlac Charter Member Join Date: May 2001 Location: Golden State Posts: 2,356
Quote:

(i) In the following simultabeous equations, the number k is not known, but it is known that when the row-reduction method is applied to the equations, they will have no solution. Find the value that k must have.

x + y + 3z = 2,
5x + 6y + 10z = 9,
2x + y + kz = 9.

(ii) Make k = 7 in the equations in (i), and solve the equations.

--------------------------------------------------------------------------------------------------------
The easiest way to do this problem is to just calculate the determinant of the matrix

1 1 3
5 6 10
2 1 k

to be 1(6k-10)-(5k-20)+3(5-12) = k - 11. Set this to zero to find that k = 11 will make the matrix singular and the system of equations to have no solutions. You can also grind through the basic row operations to end up with k-11 where the k is in the original matrix. And k=11 again will render the system unsolvable. And part (ii) is easy.
#13
05-24-2004, 07:39 PM
 TJdude825 Guest Join Date: Feb 2000
Quote:
 Originally Posted by SimonMoon5 Also, for the binomial theorem problem, well... You should know that the binomial theorem tells you how to expand (a+b)^n. In fact, you can find the coefficent for any term that you want. For the problem you're given, though, you have two polynomials that you need to expand. I'd say, first use the binomial theorem to find the first few terms of (1-x)^5. (You won't need more than the constant term, the x term, the x^2 term, and the x^3 term.) Then, do the same for (1 + 2x)^6. Now, that you've satisfied the "use the binomial theorem" requirement for this problem, use algebra to multiply out the product of these polynomials (or at least the constant through x^3 terms). Then, you'll have a bunch of terms. Combine like terms. Find the x^3 term. Look at its coefficient. Write down the coefficient as the answer.
Damn. I misread that and thought you did it totally wrong, then realized this whole post was for nothing. It was a good post too. Anyway, what I can add is that in general, the kth term of the expansion of (a+b)^n is

n!/[(n-k)!k!] * akb(n-k)

This next part is basically restating what SimonMoon5 said, because I didn't read carefully, as I said. But anyway...

I think you then need to use that formula to get the x^0 (i.e. constant), x^1 (i.e. x), x^2, and x^3 terms for both (1 - x)^5 and (1 + 2x)^6, then multiply the x^0 of one by the x^3 of the other and then the x^1 of one by the x^2 of the other, which I think gives you four different x^3 terms. Then you add all those up, and there's your answer.

( )
#14
05-24-2004, 07:56 PM
 ultrafilter Guest Join Date: May 2001
Quote:
 Originally Posted by bryn2kay Once again, many thanks for helping! I think induction is just one of those things that is very easy, but I'll have to practice a few questions before it sinks in. It amazes me how powerful a tool it is though
Induction is a howitzer: it solves all kinds of problems, but it lacks finesse, and can obscure details. In a lot of cases, you can learn more about a problem by solving it without induction than with.

For the particular example you give, induction is the only commonly-taught method that will work, but if you know anything about difference operators, there's a slightly more elegant solution.
#15
05-24-2004, 07:59 PM
 ultrafilter Guest Join Date: May 2001
Quote:
 Originally Posted by SimonMoon5 Also, for the binomial theorem problem, well... You should know that the binomial theorem tells you how to expand (a+b)^n. In fact, you can find the coefficent for any term that you want. For the problem you're given, though, you have two polynomials that you need to expand. I'd say, first use the binomial theorem to find the first few terms of (1-x)^5. (You won't need more than the constant term, the x term, the x^2 term, and the x^3 term.) Then, do the same for (1 + 2x)^6. Now, that you've satisfied the "use the binomial theorem" requirement for this problem, use algebra to multiply out the product of these polynomials (or at least the constant through x^3 terms). Then, you'll have a bunch of terms. Combine like terms. Find the x^3 term. Look at its coefficient. Write down the coefficient as the answer.
If you have two polynomials p(x) and q(x), the coefficient of xk of p(x)q(x) is given by sum(piqk-i, 0 < i < k). This is a nice formula to know.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     Straight Dope Chicago     General Questions     Great Debates     Elections     Cafe Society     The Game Room     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit Side Conversations     The Barn House

All times are GMT -5. The time now is 02:19 AM.