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}\)