Home » Induction

# Prove by induction a formula for the sum from 1 to ∞ of nkxn

Four of the previous exercise (here, here, here, and here, Section 10.9, Exercises #11 – #14) suggest a formula

In the formula indicates a polynomial of degree , with the term of lowest degree being and the highest degree term being (we call a polynomial of degree with highest term a monic polynomial of degree ). Use mathematical induction to prove this formula, without justifying the manipulations with the series.

Proof. For the case , we have

from the first exercise linked above (Section 10.7, Exercise #11). Letting , a degree polynomial, with term of lowest degree being and term of highest degree being . Therefore, the statement holds for the case . Assume then that the statement is true for some , so

Differentiating both sides (assuming without justification that we can do this) we obtain

where is a polynomial of degree with the term of lowest degree being and that of the highest degree being . Hence, if the statement is true for then it is true for ; thus, the statement is true for all positive integers

# Prove a formula for the 2nth derivative of x sin (ax)

Define and prove the formula for the th derivative of ,

Proof. The proof is by induction. For the case we need to take two derivatives of (since ).

So, the formula holds for the case . Assume then that the formula is true for some positive integer . Then the inductive hypothesis is that,

Now, we want to take two derivatives (to get a formula for ).

Now, we take another derivative,

Thus, the formula holds for . Hence, it holds for all positive integers

# Prove some properties of a differentiable function satisfying a given functional equation

Let be a function differentiable everywhere such that

1. Prove that and conjecture and prove a similar formula for .
2. Conjecture and prove a formula for in terms of for all positive integers .
3. Prove that and compute

4. Prove that there exists a constant such that

for all . Find the value of the constant .

1. Proof. We can compute this using the functional equation:

Next, we conjecture

Proof. Again, we compute using the functional equation, and the above formula for ,

2. We conjecture

Proof. The proof is by induction. We have already established the cases and (and the case is the trivial ). Assume then that the formula holds for some integer . Then we have

Thus, if the formula holds for , it also holds for . Hence, by induction it holds for all integers

3. Proof. Using the functional equation

Then, since the derivative exists for all (by hypothesis) we know it must exist in particular at . Using the limit definition of derivative, and the facts that and we have

4. Proof. Since the derivative must exist for all (by hypothesis) we know that the limit

must exist for all . Using the functional equation for we have

But then, from part (c) we know and from this exercise (Section 6.17, Exercise #38) we know

Therefore, we have

# Prove some inequalities using the function ex-1-x

1. Define a function:

Prove that for all and for all . Prove the following inequalities are valid for all ,

2. Using integration and part (a) prove

3. Using integration and part (a) prove

4. State and prove a generalization of the inequalities above.

1. First, we take the derivative of ,

Since is strictly increasing everywhere (since for all ) we have for and for . Thus, has a minimum at and so for all . Therefore, when ; hence,

Furthermore, when we have

Therefore, if then and so we have

2. Using the inequalities in part (a) we integrate over the interval to ,

For the other inequality we proceed similarly,

3. We use the same strategy as before, starting with the inequalities we established in part (b),

Similarly, for the other inequality,

4. Claim: The following general inequalities hold for all :

Proof. The proof is by induction. We have already established the inequalities for the case for all three inequalities. Now, to prove the first inequality assume

Then we have

This establishes the first inequality. For the second inequality we have proved the case already. Assume

Since is odd we may write for some nonnegative integer . We want to show that the inequality must hold for the next odd integer, . We have,

We want to show that the inequality holds for so we integrate both sides again,

Hence, if the inequality holds for odd , then it also holds for the next odd number, . Hence, it holds for all positive, odd integers.
The exact same induction argument works for all of the even integers (starting with the case we proved in part (c))

# Prove Leibniz’s formula

If is a product of functions prove that the derivatives of are given by the formula

where

is the binomial coefficient. (See the first four exercises of Section I.4.10 on page 44 of Apostol, and in particular see Exercise #4, in which we prove the binomial theorem.)

Proof. The proof is by induction. Letting and we use the product rule for derivatives

So, the formula is true for the case . Assume then that it is true for . Then we consider the st derivative :

Here, we use linearity of the derivative to differentiate term by term over this finite sum. This property was established in Theorem 4.1 (i) and the comments following the theorem on page 164 of Apostol. Continuing where we left off we apply the product rule,

where we’ve reindexed the first sum to run from to instead of from to . Then, we pull out the term from the first sum and the term from the second,

Now, we recall the law of Pascal’s triangle (which we proved in a previous exercise) which establishes that

Therefore, we have

Hence, the formula holds for if it holds . Therefore, we have established that it holds for all positive integers .

# Prove formulas for the nth derivative of sin and cos

Let

Prove that

Proof. The proof is by induction. For we have

These equalities follow from the co-relations of sine and cosine (Theorem 2.3 part (d) on page 96 of Apostol). Thus, the formulas are true for the case . Assume then that they are true for some . For we then have

Similarly, for we have

Therefore, the theorem follows by induction for all positive integers

# Compute the derivatives of g(x) = xn f(x)

Assume is a polynomial with . Define

Compute the values of .

Assume is a non-negative integer (otherwise is undefined at ). Then, we make the following claim:

Claim: The polynomial has derivatives at 0 given by the following

Proof. Since is a polynomial we may write,

Furthermore, since is given we know . Now, multiplying by we have

Next, we will use induction to prove that the th derivative of for is given by

for constants . Since the derivative is given by

for constants , we see that the formula holds for . Assume then that it holds for some ,

Then, taking the derivative of this we have,

Hence, the formula holds for all . But then, if we have

If then for all ; hence,

# Find and prove a formula for the derivative of a product of n differentiable functions

Let

be the product of functions with derivatives . Find a formula for the derivative of , and prove that it is correct by mathematical induction.

Furthermore, show that

for those at which for any .

Claim: If , then

Proof. For the case , from the usual product rule we have

Thus, our claimed formula holds in this case. Assume then that it is true for some integer . Then, if we have,

Therefore, if the formula holds for then it also holds for ; thus, it holds for all positive integers

Next, we prove the formula for the quotient, .

Proof. Let be defined as above, and let be a point at which for any . Then,

# Find the zeros of sin and cosine

1. Prove that if and only if for .
2. Find all such that .

1. Proof. First, since implies that if then , it is sufficient to show the statement holds for all (and noting that ).

From Theorem 2.3 (Apostol, Section 2.5) we know . Hence, the statement holds for the case and . Now, we use induction twice, first for the even integers, and then for the odd integers.

Assume the statement is true for some even , i.e., . Then, using the periodicity of the sine function

Hence, the statement is true for all even .

Next, assume it is true for some odd . Then,

Hence, it is true for all odd . Therefore, it is true for all nonnegative integers , and hence, for all .

Conversely, we must show that these are the only real values for which sine is 0. By the periodicity of sine, it is sufficient to show it true over any interval. We choose the interval and show for all . From above, we know . Then, from the fundamental properties of the sine and cosine, we have the inequalities,

Hence, both and are positive on . But, from the co-relation identities, we know

Thus, for (since for .) But, we also know . Hence, for we have . Since is an odd function,

Therefore, for . Therefore, we have for

2. Claim: if and only if .

Proof. Since we apply part (a) to conclude

(where we’ve just pulled an extra factor of out of to make this addition so that our answer looks like the one in the book)

# Fundamental properties of polynomials

Consider a polynomial of degree ,

1. Prove that if and then there is an degree polynomial such that .
2. Prove that is a polynomial of degree for any .
3. Prove that if and , then , for a polynomial of degree .
4. If has real zeros (i.e., there exist numbers such that ), then for all , and for all .
5. If

is a polynomial of degree , and if

for distinct , then

1. Proof. First,

Thus,

where is then an degree polynomial

2. Proof. We compute, using the binomial theorem,

Now, we want to group together the coefficients on the like-powers of . So we pull out the terms corresponding to , , etc. This gives us,

In the final line, we rewrote the coefficients as sums to view them a little more concisely. Either way, since and all of the ‘s are constants, we have is some constant for each , say and we have,

Hence, is a polynomial of degree

3. Proof. From part (b) we know that if is a polynomial of degree , then is also a polynomial of the same degree. Further,

So, by part (a), we have

where is a polynomial of degree . Thus,

But, if is a polynomial of degree , then by part (b) again, so is . Hence,

for a degree polynomial, as requested

4. Proof. The proof is by induction. First, we consider the case in which . Then . Since the assumption is that there are distinct real such that , we know there exist such that

Thus,

Hence, the statement is true for . Assume that it is true for some . Then, let be a polynomial of degree with distinct real zeros, . Then, since , using part (c), we have,

where is a polynomial of degree . Further, we know there are distinct values such that . (Since for and for with since all of the are distinct.) Thus, by the induction hypothesis, every coefficient of is 0 and for all . Thus,

But, since all of the coefficients of are zero, we have for . Hence,

Thus, all of the coefficients of are zero and for all . Hence, the statement is true for the case , and therefore, for all

5. Proof. Let

where for (we have by assumption).
Then, there are distinct real for which . (Since there are distinct real values for which , and so at each of these values .) Thus, by part (d), for and for all . But then,

and

for all . Further, since for , and by assumption for , we have for . But then,

means is a polynomial of degree as well