Solution: There are several special cases that are interesting to look at before we make a guess as to what type of function will be. First we consider the case . This immediately gives

.

It should not be too difficult to guess that is a solution to this, as well as any constant multiple of it. Now try and , resulting in

.

Looks a lot like Fibonacci, right? In fact, one possible function is just . That’s pretty convenient.

Notice how both of these illuminating examples are exponential functions, which leads us to guess that our function will be exponential as well. So, following this track, we set

so we simply need to solve

.

Unfortunately, the equation does not always have a solution (take and for example). But that’s ok and I’ll worry about it some other time. In any case we have found a function for whenever the equation has a solution in the reals.

Solution: Looking at that all too common denominator, we do a partial fraction decomposition in hopes of telescoping series. The summation becomes

.

Common Taylor series knowledge tells us that

,

which convenient fits the first part of the summation. As for the second part, we get

from the same Taylor series. Combining the results, our answer is then

.

QED.

——————–

Comment: Even though the trick at the beginning didn’t actually get much to telescope, the idea certainly made it easier to recognize the Taylor series. Algebraic manipulations are nifty to carry around and can be applied in problems wherever you go.

——————–

Practice Problem: Show that .

Solution: The adjective complicated is only placed so that we assume there is no easy way to solve to immediately give the solution. We seek an algorithm that will lead us to a local minimum (hopefully a global minimum as well).

We start at an arbitrary point . Consider the following process (for ), known as gradient descent:

1. Calculate (approximately) .

2. Set , where is a constant that can be determined by a linesearch.

It is well-known that the direction of the gradient is the direction of maximum increase and the direction opposite the gradient is the direction of maximum decrease. Hence this algorithm is based on the idea that we always move in the direction that will decrease the most. Sounds pretty good, right? Well, unfortunately gradient descent converges very slowly so it is only really useful for smaller optimization problems. Fortunately, there exist other algorithms but obviously they are more complex, such as the nonlinear conjugate gradient method or Newton’s method, the latter of which involves the computation of the inverse of the Hessian matrix, which is a pain.

.

——————–

Problem: Evaluate , where is the boundary of the region enclosed by and .

Solution: First, verify that this region satisfies all of the requirements for Green’s Theorem – indeed, it does. So we may apply the theorem with and . From these, we have and . Then we obtain

.
But clearly this integral over the region can be represented as , so it remains a matter of calculation to get the answer. First, we evaluate the inner integral to get

.

Then finally we have

.

QED.

——————–

Comment: To me, Green’s Theorem is a very interesting result. It’s not at all obvious that a line integral along the boundary of a region is equivalent to an integral of some partial derivatives in the region itself. A simplified proof of the result can be obtained by proving that

and .

——————–

Practice Problem: Let be a plane region with area whose boundary is a piecewise smooth simple closed curve . Show that the centroid of is given by

and .

,

i.e. the determinant of the matrix of the partial derivatives (also known as the Jacobian matrix). Naturally, this can be generalized to more variables.

——————–

Theorem: If the transformation , maps the region in the -plane into the region in the -plane, and if the Jacobian is nonzero and does not change sign on , then (with appropriate restrictions on the transformation and the regions) it follows that

.

——————–

Problem: Evaluate , where is the region in the first quadrant enclosed by the trapezoid with vertices .

Solution: The bounding lines can be written as , , , and . Now consider the transformation and . In the -plane, the bounding lines of the new region can now be written as , , , and .

We can write and as functions of and : simply and . So the Jacobian .

Then our original integral becomes . And this is equivalent to

.

QED.

——————–

Comment: Note that the above theorem is probably very important in multivariable calculus, as it is the equivalent to -substitution in one variable, which we all know is the ultimate integration technique. It functions in the same way, giving you a lot more flexibility on the function you are integrating and the region you are integrating on.

——————–

Practice Problem: Evaluate , where is the rectangular region enclosed by the lines , , , .

exists, then the following limit also exists and we have

.

——————–

Theorem: (Summation by Parts) If and are two sequences, then

.

——————–

Problem: Let be a sequence of real numbers such that converges. Show that .

Solution: Define the sequence by and let . Then, by summation by parts with and , we have

.

The summation we wish to take the limit of is then

.

But since, by Stolz-Cesaro,

,

we obtain

.

QED.

——————–

Comment: Summation by parts is a very useful technique to change sums around so that they are easier to evaluate. If you hadn’t noticed, it is the discrete analogue of integration by parts and is in fact very similar. Stolz-Cesaro is powerful as well and seems like a discrete analogue to L’Hopital (but I’m not sure about this one). Applying well-known calculus ideas to discrete things can often turn into neat results.

——————–

Practice Problem: If is a decreasing sequence such that , show that

converges for all .

——————–

Definition: Let be a real-valued function defined on a convex set . We say that is convex if, for all and , we have

.

——————–

Theorem: (Jensen’s Inequality) Let be a real-valued, convex function defined on a convex set . Given and nonnegative reals such that , we have

or, more concisely,

.

Proof: We proceed by induction on .

Base Case – , we have which is trivially true. , we have with which is true by the definition of convexity.

Induction Step – Suppose . We wish to show

for nonnegative reals that sum to . Well,

by the definition of convexity. But since , by our inductive hypothesis (the term case) we must have

.

Combining this into the above inequality, we obtain

as desired, completing the induction. QED.

——————–

Definition: The convex hull of a set is defined to be the smallest convex set containing . It is the set of all points that can be written as , where is a natural number, are nonnegative reals that sum to , and .

——————–

Definition: A vertex of a set is a point such that for all not equal to and we have .

——————–

Theorem: Let be the set of vertices of a compact convex set . The convex hull of is .

Example: The set of vertices of a convex polygon is, in fact, its vertices as traditionally defined in geometry. Any point inside the polygon can be written as a convex combination of its vertices.

——————–

Theorem: If is a real-valued, convex function defined on a compact convex set , then , where is the set of vertices of .

Proof: We will show that for all .

Let where are nonnegative reals that sum to and . This is possible by the preceding theorem. Then by Jensen’s Inequality we get

.

And since , we have for all . Furthermore, since is a subset of , we know that this maximum is attained, thus

as desired. QED.

——————–

Comment: This is a very useful result, as it allows us to limit our search for the maximum of a function to its set of vertices, which is usually a considerably smaller set, though it may still be infinite (think sphere). In any case, this works well for constrained optimization problems in which the domain is limited to a polygon, the easiest application of this theorem.

——————–

Practice Problem: Let and be real numbers satisfying and . Find the maximum value of .

Solution: So, testing some small numbers yields as a solution. We claim that this is the only such solution.

Clearly, since is a square, we can use a variant of the usual prime decomposition and say that .

Furthermore, again since is a square, we know

is odd, so must be odd as well, i.e. is not one of the . Then we use the equation given to us to get

.

Note, however, that by Bernoulli’s Inequality (overkill, I know) we have for

with equality iff and . So

.

Since we want equality, we must have and for all . But since the primes are supposed to be distinct we can have exactly one prime so that is the only solution. QED.

——————–

Comment: Another one of those problems that you kind of look at the result and you’re like huh, that’s interesting. But anyway, just throwing in some weak inequalities led to a pretty straightforward solution. As long as you know how to find the number of divisors of a positive integer it isn’t too much of a stretch to figure the rest out, though it make take some time to get in the right direction since the problem is quite open-ended.

——————–

Practice Problem: (1999 Canada – #4) Suppose are eight distinct integers from . Show that there is an integer such that the equation has at least three different solutions. Also, find a specific set of distinct integers from such that the equation does not have three distinct solutions for any .

Solution: Let . Then , a well-known Taylor series. So we want to integrate this:

by parts using and . Substituting in the last integral, we have

.

So . Thus

for some constant . Using our knowledge that , , and by L’Hopital twice, we see that

Then setting we obtain and . QED.

——————–

Comment: This was a pretty tough problem that required you to compound a lot of calculus knowledge all into a single problem – series, integration by parts, limits. Recognizing all the steps was the first part; following through with the right computations was another. Still, there weren’t really any super clever tricks, mostly just standard substitutions and approaches applied in a somewhat non-standard way. Makes for a very nice problem.

——————–

Practice Problem #1: Show that .

Practice Problem #2: Evaluate . Can you also find ?

Solution: Consider the polynomial . We have

,

so we want to factor the second term when . Call it so that . Consider the relation

.

Since is a root of the LHS, we factor it out of the RHS as well to get

.

Dividing through by and rearranging, we obtain the nice expression

.

Letting , this becomes

which is conveniently enough a difference of two squares. And we’ll leave it as this because the factors are not particularly nice or anything. QED.

——————–

Comment: This “natural” factorization was basically the one crucial step to solving the USAMO #5 this year and most people did not see it, unsurprisingly. Taking the difference was the trickiest/cleverest part, and there were definitely a limited number of approaches to this factorization. Oh well, at least it seems sort of cool after you know about it.

——————–

Practice Problem: (2007 USAMO – #5) Prove that for every nonnegative integer n, the number is the product of at least (not necessarily distinct) primes.