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:
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).
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.
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.
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
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.
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)
Problems like this are generally solved using generating functionals. Here’s the basic idea:
[ol]
[li]Define an infinite polynomial G(x) in some variable x such that[/li]
G(x) = f(0) + f(1)x + f(2)x[sup]2[/sup] + f(3)x[sup]3[/sup] + …
Don’t worry about convergence, etc. of this polynomial; it’s really just an infinite set of placeholders (as we’ll see below.)
[li]Rewrite the above recursion relation as[/li]
f(n+1) - 5 f(n) + 6 f(n-1) = 0
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 x[sup]2[/sup] is f(2) - 5 f(1) + 6 f(0), which is zero because of the recursion relation. Adding the polynomials therefore gives us
[li]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[/li]
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)[sup]2[/sup] + (nx)[sup]3[/sup] + … This means that
and so, identifying coefficients, f(n) = 2*3[sup]n[/sup] + 2[sup]n[/sup].
[/ol]
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.
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
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.
Damn. I misread that and thought you did it totally wrong, then realized this whole post was for nothing. :smack: 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
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.
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.
If you have two polynomials p(x) and q(x), the coefficient of x[sup]k[/sup] of p(x)q(x) is given by sum(p[sub]i[/sub]q[sub]k-i[/sub], 0 < i < k). This is a nice formula to know.
