# MEDE2.3.16

16.  Consider the particular solution of

$$y’ + ay = e^{bx}, y = \frac{e^{bx}}{b + a}$$.

Show how a particular solution can be obtained for

$$y’ + ay = x$$

by differentiation with respect to $$b$$, followed by $$b = 0$$.

Solution:

First we differentiate $$y$$ with respect to $$b$$ to get:

$$\frac{dy}{db} = \frac{e^{bx}}{b+a}\left(x – \frac{1}{b+a}\right)$$

Next, we find $$y’$$ (differentiate with respect to $$x$$) and then differentiate with respect to $$b$$:

$$y’ = \frac{be^{bx}}{b+a} = by$$

$$\frac{dy’}{db} = y + b\frac{dy}{db}$$

If we differentiate the right-hand side of the original differential equation we simply get $$\frac{d}{db}e^{bx} = xe^{bx}$$. We therefore get the new differential equation:

$$\frac{d}{db}\left(y’ + ay\right) = \frac{d}{db}e^{bx}$$

$$y + (b + a)\frac{dy}{db} = xe^{bx}$$

$$\frac{e^{bx}}{b+a} + e^{bx}\left(x – \frac{1}{b+a}\right) = xe^{bx}$$

$$\frac{1}{b+a} + x – \frac{1}{b+a}= x$$

$$x = x$$

Thus the method of differentiating with respect to $$b$$ has proven to be a successful method of finding a solution to the new differential equation. We can now proceed to the second part of the question.

If we set $$b = 0$$ in our earlier solution for $$\frac{dy}{db}$$, we get a new particular solution $$y = \frac{x-1}{a}$$.

We can check the validity of this solution easily:

$$y’ = \frac{1}{a}$$

$$\frac{1}{a} + \frac{x-1}{a} = x$$

# MEDE2.3.1

1. Find the solution of

1. $$y’ + 2y = x$$,      $$y(0) = 1$$,
2. $$y’ – y = \sin x$$,     $$y(0) = 2$$.

Solution:

For part a we use the fact that $$\frac{d}{dx}\left(ye^{2x}\right) = y’e^{2x} + 2ye^{2x}$$. Multiplying both sides of the equation by $$e^{2x}$$ we get:

$$e^{2x}\left(y’ + 2y\right) = xe^{2x}$$

$$\frac{d}{dx}\left(ye^{2x}\right) = xe^{2x}$$

Integrating between $$0$$ and $$x$$, we get:

$$ye^{2x} – y(0) = \int_o^x x_1e^{2x_1}dx_1$$

Now we’ll use integration by parts:

$$u = x, u’ = dx, v = e^{2x}, v’ = 2e^{2x}dx, d(uv) = u’v + uv’$$

$$\int_o^x x_1e^{2x_1}dx_1 = \frac{1}{2} \int_0^x uv’ = \frac{1}{2} \left(\int_0^x d(uv) – \int_0^x u’v\right) = \frac{1}{2}\left(xe^{2x} – \frac{1}{2}\left(e^{2x} – 1\right)\right)$$

$$ye^{2x} – 1 = \frac{(2x-1)e^{2x}+1}{4}$$

$$y = \frac{2x-1 + 5e^{-2x}}{4}$$

For part b, we use the same strategy, knowing that $$\frac{d}{dx}\left(ye^{-x}\right) = y’e^{-x} – ye^{-x}$$:

$$e^{-x}\left(y’ – y\right) = e^{-x}\sin x$$

$$\frac{d}{dx}\left(e^{-x}y\right) = e^{-x}\sin x$$

Again, we integrate between $$0$$ and $$x$$:

$$e^{-x}y – y(0) = \int_0^x e^{-x_1}\sin x_1 dx_1$$

If we use the exponential form of sine,

$$\sin(x) = \frac{1}{2i}\left(e^{ix} – e^{-ix}\right)$$,

we get:

$$\int_0^x e^{-x_1}\sin x_1 dx_1 = \frac{1}{2i}\left(\int_0^x \left(e^{(i-1)x_1} – e^{-(i+1)x_1}\right)dx_1 \right) = \frac{1}{2i}\left(\frac{1}{i-1}e^{(i-1)x} + \frac{1}{i + 1}e{-(i+1)x} – \frac{1}{i-1} – \frac{1}{i + 1}\right)$$

$$e^{-x}y – 2 = \frac{(i+1)e^{(i-1)x} + (i-1)e^{-(i+1)x_1} – 2i}{-4i}$$

$$y = \frac{(i-1)e^{ix} + -(1+i)e^{-ix} + 2}{4} + 2e^x$$

Using the exponential forms of sine and cosine, we get back to the trigonometric form:

$$y = \frac{-2\cos(x) – 2\sin(x) + 2e^x}{4} + 2e^x$$

$$y = -\frac{1}{2}\left(\cos(x) + \sin(x) – 5e^x\right)$$

# IMO.2006.4

4. Determine all pairs $$(x, y)$$ of integers such that

$$1 + 2^x + 2^{2x+1} = y^2$$.

Solution:

I started off with a bit of circuitous completing-the-square rearrangement:

$$\left(1 + 2^{x-1}\right)^2 = 2^{2x-2} + 2^x + 1$$

$$\left(1 + 2^{x-1}\right)^2 – 2^{2x-2} + 2^{2x+1} = y^2$$

$$2^{2x-2}\left(2^3 – 1\right) = y^2 – \left(1 + 2^{x-1}\right)^2$$

$$2^{2x-2}\cdot 7 = \left(y – \left(1 + 2^{x-1}\right)\right)\left(y + \left(1 + 2^{x-1}\right)\right)$$

Either $$(y – 1 – 2^{x-1})$$ or $$(y +1 + 2^{x-1})$$ must be of the form $$2^a$$ for some integer $$a$$ and the other must be of the form $$2^b\cdot 7$$ for some integer $$b$$ where $$a + b = 2x-2$$.

We can take the difference of both these expression (and thus cancel out the $$y$$ terms) in two possible ways.

Here is the first:

$$2^{2x – 2 – b} – 2^b\cdot7 = (y – 1 – 2^{x-1}) – (y + 1 + 2^{x-1}) = -2 – 2^x$$

$$2^{2x – 2 – b} – 2^b\cdot7 = -2^x – 2$$

$$2^b\cdot7 = 2^x + 2^{2x-2-b} + 2$$

$$7 = 2^{x-b} + 2^{2x-2-2b} + 2^{1-b}$$

Since 7 is odd, we know that one of the terms in the sum must be equal to $$2^0 = 1$$ and that all the exponential terms must be positive integers. This leaves us with $$b = 1$$ or $$b = x-1$$.

For $$b=1$$, we get $$6 = 2^{x-1} + 2^{2x – 4}$$ which has no integral solutions.

For $$b=x-1$$, we get $$6 = 2^1 + 2^{2-x}$$, which yields the solution $$x=0$$ and $$y=\pm 2$$.

The second difference changes the signs on our first and third terms:

$$7 = – 2^{x-b} + 2^{2x-2-2b} – 2^{1-b}$$

For this difference, our middle term (the only positive one) must be greater than 7 and therefore it cannot be our $$2^0$$ term. Thus our only solution is $$b = 1$$, we get:

$$8 = -2^{x-1} + 2^{2x-4}$$

$$1 = -2^{x-4} + 2^{2x-7}$$

Using the same logic as before, 1 is an odd number therefore one of the terms must be equal to $$2^0$$. The only possibility is for $$x=4$$, and yields the solution $$y=\pm 23$$.

Thus there are four integer solutions, $$(0, \pm 2)$$ and $$(4,\pm 23)$$.

# ITFL1.2

1.2 Find a context-free grammar to generate each of the following languages:

1. $$L = \lbrace a^ib^j|i = 0, 1,…,j = 0,1,…,\mbox{ and } j \geq i \rbrace$$
2. $$L = \lbrace a^ib^ja^jb^i|i = 0, 1,…,j = 0,1,… \rbrace$$
3. $$L = \lbrace a^ib^ia^jb^j|i = 0, 1,…,j = 0,1,… \rbrace$$
4. $$L = \lbrace a^ib^i|i = 0, 1,…\rbrace \cup \lbrace b^ja^j|j = 0,1,…\rbrace$$
5. $$L = \lbrace PP^{-1}|P \in \lbrace a, b \rbrace^* \rbrace$$
6. $$L = \lbrace a^ib^jc^{i+j}|i = 0, 1,…,j = 0,1,…\rbrace$$

Solution:

1. $$G = \left( \lbrace S \rbrace,\lbrace a,b \rbrace, S, \lbrace S \rightarrow \lambda, S \to aSb, S \to Sb \rbrace \right)$$
2. $$G = \left( \lbrace S, T \rbrace,\lbrace a,b \rbrace, S, \lbrace S \rightarrow \lambda, S \to aSb, S \to T, T \to bTa, T \to \lambda \rbrace \right)$$
3. $$G = \left( \lbrace S, T \rbrace,\lbrace a,b \rbrace, S, \lbrace S \rightarrow \lambda, S \to TT, T \to \lambda, T \to aTb \rbrace \right)$$
4. $$G = \left( \lbrace S, L, R \rbrace,\lbrace a,b \rbrace, S, \lbrace S \rightarrow L, S \to R, L \to \lambda, R \to \lambda, L \to aLb, R \to bRa \rbrace \right)$$
5. $$G = \left( \lbrace S \rbrace,\lbrace a,b \rbrace, S, \lbrace S \rightarrow \lambda, S \to aSa, S \to bSb \rbrace \right)$$
6. $$G = \left( \lbrace S, T \rbrace,\lbrace a,b,c \rbrace, S, \lbrace S \rightarrow \lambda, S \to aSc, S \to T, T \to bTc, T \to \lambda \rbrace \right)$$

# ITFL1.1

1.1 Show that the grammar

$$G = \left( \lbrace S \rbrace,\lbrace a,b \rbrace, S, \lbrace S \rightarrow \lambda, S \to aSb \rbrace \right)$$

generates the language

$$L = \lbrace a^ib^i|i = 0, 1, . . . \rbrace$$

Solution:

We can use the inductive method for this proof. For $$i = 0$$, we get $$\lambda$$, and likewise we can go straight from the initial symbol $$S$$ to $$\lambda$$ using the first rewriting rule. If we assume that $$a^kb^k$$ can be generated by G, then $$a^kSb^k$$ must have been the penultimate state of the rewriting process. Using the second rewriting rule, $$a^kSb^k$$ will also generate $$a^{k+1}b^{k+1}$$ and the proof is complete.

# NT1-1.18

18. Prove that if $$n$$ is an odd positive integer, then $$x + y$$ is a factor of $$x^n + y^n$$. (For example, if $$n=3$$, then $$x^3 + y^3 = (x+y)(x^2 – xy + y^2)$$.)

Solution:

Let $$P_n = x^{2n-1} + y^{2n-1}$$ and $$Q = x + y$$. $$P_1 = x + y = Q$$ and therefore $$P_1$$ is divisible by $$Q$$ and the first step of induction is done.

$$P_{k+1} = x^{2k + 1} + y^{2k + 1} = x^2\cdot x^{2k-1} + y^2\cdot y^{2k-1}$$

$$P_{k+1} = x^2P_k + y^2P_k – (x^2\cdot y^{2k-1} + y^2\cdot x^{2k-1})$$

$$P_{k+1} = x^2P_k + y^2P_k – x^2y^2(y^{2k-3} + x^{2k-3})$$

$$P_{k+1} = x^2P_k + y^2P_k – x^2y^2P_{k-1}$$

$$P_k$$ and $$P_{k-1}$$ are both assumed to be divisible by $$Q$$ as part of the inductive method, therefore all the terms are divisible by $$Q$$ and thus $$P_{k+1}$$ is divisible by $$Q$$

# NT1-1.17

17. Prove that $$n(n^2 – 1)(3n + 2)$$ is divisible by 24 for each positive integer $$n$$.

Solution:

For $$n = 1$$ we get the trivial case of 0.

$$S_n = n(n^2 – 1)(3n + 2)$$

$$S_{n+1} = (n+1)((n+1)^2 – 1)(3(n+1) + 2) = (n+1)(n^2 + 2n + 1 – 1)(3n + 5)$$

$$S_{n+1} = n((n^2 – 1)(3n + 5) + (2n + 1)(3n + 5)) + (n^2 – 1)(3n + 5) + (2n + 1)(3n + 5)$$

$$S_{n+1} = n((n^2 – 1)(3n + 2) + (2n + 1)(3n + 5) + 3(n^2-1)) + (n^2 – 1)(3n + 5) + (2n + 1)(3n + 5)$$

$$S_{n+1} = n(n^2 – 1)(3n + 2) + n(2n + 1)(3n + 5) + 3n(n^2 -1) + (n^2 – 1)(3n + 5) + (2n + 1)(3n + 5)$$

$$S_{n+1} = S_n + n(2n + 1)(3n + 5) + 3n(n^2 -1) + (n^2 – 1)(3n + 5) + (2n + 1)(3n + 5)$$

Since we can assume that $$S_n$$ is divisible by $$24$$, we no longer need to worry about it so we are left with

$$n(2n + 1)(3n + 5) + 3n(n^2 -1) + (n^2 – 1)(3n + 5) + (2n + 1)(3n + 5)$$

$$(n+1)(2n + 1)(3n + 5) + (n^2 – 1)(6n + 5)$$

$$(2n^2 + 3n + 1)(3n + 5) + 6n^3 + 5n^2 – 6n – 5$$

$$6n^3 + 19n^2 + 18n + 5 + 6n^3 + 5n^2 – 6n – 5$$

$$12n^3 + 24n^2 + 12n$$

$$12n(n+1)^2$$

Since 12 is a constant factor, all we need is for either of the other terms to be divisible by 2. If n is even, then that suffices. If n is odd, then $$n+1$$ will be even and the proof is finished.

# NT1-1.16

16. Prove that

$$L_1 + 2L_2 + 4L_3 + 8L_4 + . . . + 2^{n-1}L_n = 2^nF_{n+1} – 1$$.

$$F_n$$ and $$L_n$$ stand for the $$n$$th Fibonacci and Lucas terms, respectively.

Solution:

Let’s represent the left-hand side of the equation as $$F_k = \sum_{n=1}^k 2^{n-1}L_n$$ and represent the right-hand side as $$G_k = 2^kF_{k+1} – 1$$. First step of induction is to show that $$F_1 = L_1 = 1$$ and that $$G_1 = 2 \cdot F_2 – 1 = 2 – 1 = 1$$. The next step proceeds as follows:

$$G_{k+1} = 2^{k+1}F_{k+2} – 1$$

$$F_{k+1} = F_k + 2^kL_{k+1}$$

$$F_{k+1} = 2^kF_{k+1} – 1 + 2^kL_{k+1} = 2^k\left(F_{k} + F_{k+1} + F_{k+2}\right) – 1$$

$$F_{k+1} = 2^k\left(2F_{k+2}\right) – 1 = 2^{k+1}F_{k+2} – 1$$

# NT1-1.14

14. What is wrong with the following argument?

Assuming $$L_n = F_n$$ for $$n = 1, 2, . . ., k$$, we see that

$$\begin{array}{r l l} L_{k+1} & = L_k + L_{k-1} & \mbox{ (by Exercise 13)}\\ & = F_k + F_{k-1} & \mbox{ (by our assumption)}\\ & = F_{k+1} & \mbox{ (by definition of }F_{k+1}\mbox{).}\end{array}$$

Hence, by the principle of mathematical induction, $$F_n = L_n$$ for each positive integer $$n$$.

$$F_n$$ and $$L_n$$ stand for the $$n$$th Fibonacci and Lucas number, respectively.

Solution:

The two definitions used in the proof ($$L_n = L_{n-1} + L_{n-2}$$ and $$F_n = F_{n-1} + F_{n-2}$$) are both restricted to cases where $$n \geq 3$$, therefore the first step of induction should be to test whether $$L_3 = F_3$$, which is clearly not the case and we need go no further.

# NT1-1.13

13. The Lucas numbers $$L_n$$ are defined by the equations $$L_1 = 1$$, and $$L_n = F_{n+1} + F_{n-1}$$ for each $$n \geq 2$$. Prove that

$$L_n = L_{n-1} + L_{n-2} (n \geq 3)$$.

$$F_n$$ stands for the $$n$$th Fibonacci number.

Solution:

The equality we are proving is for values of $$n \geq 3$$ so the first step of our induction needs to begin at $$n = 3$$. By the definition given for the Lucas numbers, $$L_1 = 1$$, $$L_2 = F_3 + F_1 = 2 + 1 = 3$$ and $$L_3 = F_4 + F_2 = 3 + 1 = 4$$. The proposed equality similarly yields $$L_3 = L_2 + L_1 = 3 + 1 = 4$$. Now for the second step:

$$L_{k+1} = L_{k} + L_{k-1}$$

$$L_{k+1} = \left(F_{k + 1} + F{k – 1}\right) + \left(F_{k} + F_{k – 2}\right)$$

$$L_{k+1} = \left(F_{k} + F_{k+1}\right) + \left(F_{k-1} + F_{k-2}\right)$$

$$L_{k+1} = F_{k+2} + F_{k}$$