Title: Proof
Course: Demonstrating STACK (v4.3.7)

Q: Complete the following proof.

Let \(P(n)\) be the statement

[value]

Since \( [value] =\)

and \( [value] = \)

it follows that \(P(1)\) is true.

Assume that \(P(n)\) is true.

\([value] = \)

\( = [value] + [value]\)

\( = [value]\)

\( = \)

Since \(P(1)\) and \(P(n)\Rightarrow P(n+1)\) it follows that \(P(n)\) is true for all \(n\in\mathbb{N}\) by the principal of mathematical induction.
Feedback: The complete proof is below Let \(P(n)\) be the statement [value] Since \( [value] = [value]\) and \( [value] = [value]\) it follows that \(P(1)\) is true. Assume that \(P(n)\) is true. \([value] = [value]\) \( = [value] + [value]\) (using the induction hypothesis) \( = [value]\) \( = \) [value] Since \(P(1)\) and \(P(n)\Rightarrow P(n+1)\) it follows that \(P(n)\) is true for all \(n\in\mathbb{N}\) by the principal of mathematical induction. More generally, consider the following when writing an induction proof to establish the finite sum of a series of the form \[ [value]. \] - The base case is often very easy to prove, so easy in fact that it looks pointless or trivial. The base case is just as important as the induction step! - At the start of the induction step, separate the \(n+1\)th term from the sum, so that you have \[ [value]. \] You can now apply the induction hypothesis to get \[ [value]. \] At this point the goal is to algebraically manipulate your expression so that you clearly have the expression \(P(n+1)\). That is, you should be able to rewrite \(P(n)+p_{n+1}\) as \(P(n+1)\). Sometimes the algebra is difficult, but it is often a good idea to identify common factors between \(P(n)\) and \(p_{n+1}\) and work from there. In the above example we chose to write \(2n+3\) as \(2(n+1)+1\) to make it clear that this is part of \(P(n+1)\).
  Hint: Incorrect answer.

Let \(P(n)\) be the statement [value]

1. Write the statement \(P(n+1)\):

2. Calculate \[ [value] - [value] \] writing your answer in simplified form.

3. Calculate \[ [value] - [value] \] writing your answer in simplified form.

3. Assume \(n\in\mathbb{N}\). For which values of \(n\) is the implication \(P(n) \Rightarrow P(n+1)\) true?

You may answer with an inequality, e.g. n>?, a set {?, ?, ..., ?}, or with N\(=\mathbb{N}\) or none.

4. For which values of \(n\in\mathbb{N}\) is the \(P(n)\) true?
You may answer with an inequality, e.g. n>?, a set {?, ?, ..., ?}, or with N\(=\mathbb{N}\) or none.
Feedback: 1. To write the statement for \(P(n+1)\) we must substitute \(n \to n+1\) in the statement \(P(n)\). This gives \[ [value]. \] 2. Note that \[ \sum\limits_{k=1}^{n} k \cdot k != 1 \cdot 1! + 2 \cdot 2! + \cdots + n\cdot n! \qquad \mbox{ and } \qquad \sum\limits_{k=1}^{n+1} k \cdot k! = 1 \cdot 1! + 2 \cdot 2! + \cdots + n\cdot n! + (n+1) \cdot (n+1)! \] Thus when taking the difference every term cancels apart from the final one in the second series and we are left with \(\sum\limits_{k=1}^{n+1} k \cdot k! - \sum\limits_{k=1}^{n} k \cdot k! = (n+1)(n+1)!\). 3. By definition of factorial \[ (n+2)! = 1 \cdot 2 \cdot 3 \cdots n \cdot (n+1) \cdot (n+2) \qquad \mbox{ and } \qquad (n+1)! = 1 \cdot 2 \cdot 3 \cdots n \cdot (n+1). \] Therefore \[ \begin{eqnarray*} (n+2)! - (n+1)! & = & (1 \cdot 2 \cdot 3 \cdots n \cdot (n+1) \cdot (n+2)) - (1 \cdot 2 \cdot 3 \cdots n \cdot (n+1))\\ & = & (n+2 -1) (1 \cdot 2 \cdots n \cdot (n+1)) \\ & = & (n+1) (n+1)! \end{eqnarray*} \] 4. The implication is true for all \(n \in \mathbb{N}\). 5. The statement \(P(n)\) is true for no values of \(n \in \mathbb{N}\). The whole point of this question is that, in a valid proof by induction, the base case is as important as proving that the implication \(P(n) \Rightarrow P(n+1)\) is true for all \(n\).

Complete the following proof by induction:
Prove that the sum of the first \(n\) odd natural numbers equals \(n^2\).

1.
Let \(P(n)\) be the statement
2.
The sum of the first odd number, \(1\), equals \(1^2\) so that \(P(1)\) is
3.
Assume that \(P(n)\) is true. Then
\(\sum_{k=1}^{n+1} [value] = \sum_{k=1}^{n} ([value]) + \) \( = \)
4.
Hence \(P(n+1)\) is also
5.
Since \(P(1)\) and \(P(n)\Rightarrow P(n+1)\) it follows that \(P(n)\) is true for all \(n\in\mathbb{N}\) by the principal of mathematical induction.
Feedback: Since every odd natural number has the form \(2k+1\) for \(k = 0, 1 , \dots\). the statement can be written as \[ P(n) = [value]. \] \(P(1)\) is true since \(2\cdot 1 - 1 = 1= 1^2\). We use the induction hypothesis to show that the statement \(P(n+1): \sum\limits_{k=1}^{n+1} 2k-1 = (n+1)^2\). \begin{eqnarray*} \sum\limits_{k=1}^{n+1} 2k-1 & = & \sum\limits_{k=1}^{n} 2k-1 + 2(n+1) - 1 \\ & = & n^2 + 2(n+1) - 1\\ & = & n^2 + 2n +1 \\ & = &(n+1)^2. \end{eqnarray*} Hence \(P(n+1)\) is also true.

Q: Consider the following proof.
1.
Let \(P(n)\) be the statement
2.
[value]
3.
Since
4.
\([value]=[value] \mbox{ and} [value]=[value]\)
5.
it follows that \(P(1)\) is true.
6.
Assume that \(P(n)\) is true.
7.
\([value] = [value] + [value]\)
8.
\( = [value] + [value]\)
9.
\( = [value]\)
10.
\( = [value]\)
11.
Since \(P(1)\) and \(P(n)\Rightarrow P(n+1)\) it follows that \(P(n)\) is true for all \(n\in\mathbb{N}\) by the principal of mathematical induction.

a. Which line states the induction hypothesis?

b. Write out the induction hypothesis for \(n=3\) in full, i.e. without \(\sum\), and without simplifying your answer.

c. Which lines prove the induction step?

d. In which line of the induction step is the induction hypothesis used?

e. Calculate \( 1^2+2^2+\cdots + [value]^2 = \)
Feedback: a. Line 2. states the induction hypothesis. b. The induction hypothesis is that we assume \(P(n)\) to be true. We are asked for the statement \(P(3)\) which is [value]. c. The lines proving the induction step are the lines 6-10. d. The induction hypothesis is used in step 8 where we use \(P(n)\) to substitute [value]. e. \(1^2+2^2+\cdots + [value]^2 = \sum\limits_{k=1}^75 k^2 = \frac{75 \cdot 76 \cdot 151}{6} = 143450\).
  Hint: Incorrect answer.

This result is essential for Analysis II. Please study it carefully.
Complete the proof by filling in the blanks.

Archimedean Property: For all \(x \in \mathbb{R}\), there exists \(n \in \mathbb{N}\) such that \(x < n.\)

Proof:

1) We will prove by contradiction.
Suppose, on the contrary, that \(\mathbb{R},\) \( n \in \mathbb{N}, n \le x\).

In other words, \(x\) is an upper bound of \(\mathbb{N}.\)

2) The non-empty set \(\mathbb{N}\) therefore has a \(u.\)

3) Since \(u-1 < u\), we know \(u-1\) is not of \(\mathbb{N}\) so there

exists \(m \in \mathbb{N}\) with \(u-1\) \(m.\)

4) Therefore, \(u\) \(m+1\) and since \(m+1 \in \mathbb{N}\), this contradicts

the fact that \(u\) is .

Thus, the proof is complete.

__________

Further question

Which step of the proof uses the Completeness property?

Here is a visualisation of the \(\epsilon\)-\(\delta\) definition for the continuity of a function \(f\) at the point \(x=c.\)

The curve \(y=f(x)\) is shown in blue.

You can use the slider to adjust these parameters:
- The value of \(\epsilon\)
- The position of the point \(c\).
Note that the slider has a tolerance of around \(5\times10^{-4}\), and the numbers displayed are dependent on browsers.

a) The function is continuous at \(x=1\).
For each of the following values of \(\epsilon\), write down the largest value of \(\delta\) such that: \[|x-1|<\delta\implies |f(x)-f(1)|<\epsilon.\]
(If you can't adjust the parameters to exactly these values, just use the nearest possible values.)

Give your answers to 2 decimal places.

(i) \(\epsilon=0.3\), \(\delta=\)

(ii) \(\epsilon=0.6\), \(\delta=\)

Suppose that the function is given by \(f(x)=\frac{2}{x}\). Find the exact value of the answer to part (ii). Express your answer as a fraction.

Answer: \(\delta=\)

We are going to study a function, \(\; f\colon \mathbb{R}\to \mathbb{R},\) with the following strange property:

\(\;f\) is differentiable at \(c \in \mathbb{R}\) and \(f'(c) > 0,\) yet there exists no neighbourhood of \(c\) in which \(f\) is strictly increasing.

(You should find this somewhat disturbing.)

One function with this property is:
\[f(x)=\begin{cases} x+2x^2\sin\left(\frac{1}{x}\right) & x \neq 0 \\ 0 & x=0 \end{cases}\]

The above graph shows the function \(y=f(x)\) (the blue curve), which is bounded between the upper (red) curve and the lower (green) curve. (Try the zoom in/out and shift buttons).

Give the equations of the upper and lower bounding curves.

Upper: \(y=\)

Lower: \(y=\)

Now we will show that the function \(f\) satisfies the strange property.

We start by proving that \(f'(0)>0.\)

From the definition of a derivative,

\(f'(0)=\) | \(\lim_{x\to 0} \frac{f(x)-f(0)}{x-0}\)
\(=\) | \(\lim_{x \to 0}\)()
\(=\) | .

In the last step, we use the fact that \(-2x \leq 2x\sin\left(\frac{1}{x}\right) \leq 2x\), and let \( x\to 0\) and apply the theorem.

2)We now prove that \(f\) is not locally increasing at \(x=0\).

2i) \(f\) is locally increasing at 0 iff \(\forall \delta > 0,\) \(\geq 0\) in \((-\delta,\delta).\)

2ii) Hence, it suffices to show that \(\exists c \in (-\delta,\delta)\) such that .

2iii) Now, \[f'(x)=\begin{cases} \text{?}  & x \neq 0 \\ 1 & x=0 \end{cases}\]

Fill in the missing derivative.

2iv) By the property of real numbers, \(\forall \delta > 0, \exists n \in \mathbb{N}\) such that \(0< \frac{1}{n} < 2 \pi \delta.\)

2v) Let \(c = \frac{1}{2\pi n} \in (0,\delta).\) Then \(f'(c)=\) .

Hence, the function \(f\) indeed satisfies our counterintuitive property.

This is one reason why analysis is so important: our intuition can be misleading!

This question also concerns limsup and liminf.

Consider the following sequence for some \(k \in \mathbb{Z}.\)

\[x_n= \begin{cases} [value] & \text{if} \; n = 3k \\ n^{1/n} & \text{if} \; n =3k+1 \\ \sin\left(\frac{n\pi}{3}\right) & \text{if} \; n=3k+2 \end{cases}\]

The graph below (showing each of the three functions) may be helpful. You can zoom in and shift the display window.

For the following questions, express your answers in exact form. Note that \(\pi\) can be entered by typing pi and \(\sqrt{n}\) by typing sqrt(n).

a) Write down the first 6 terms of the sequence \((x_n)\) where \(n\in\mathbb{N}\). Powers, if fractional, should be enclosed in (...).

\(x_n=\) {,,,,,...}

b) Write down the first 6 terms of the sequence \((S_n)\) where \(S_n=\sup_{i\geq n} x_i.\)

\(S_n=\)(,,,,,...)

c) Hence, \(\limsup_{n\to \infty} x_n= \lim_{n\to \infty} S_n= \)

d) Using a similar working, we find \(\liminf_{n\to \infty} x_n=\)

Let \(f\colon \mathbb{R}\to \mathbb{R}\) be given by \(f(x) = ||x|-1|-1.\)
Let us investigate the local extrema of this function.

First, you will find it extremely useful to sketch the graph of this function. Try to do it on your own, then check with Desmos, for example.

____________

a) \(\; f\) attains a local maximum at \(x=\)

Although this statement is evident from the graph, this is Analysis, so we must prove it rigorously.

Subproof 1: Consider \(x \in (-1,1).\)

i) \( -1<x<1 \implies\) \(\leq\ |x|< 1\)

ii) \(\implies\) \(\leq |x|-1<0\)

iii) \(\implies\) \(< ||x|-1| \leq\)

iv) \(\implies\) \(<||x|-1|-1 \leq\)

v) \(\implies f(x) \leq\)

____________

b) \(\; f\) has  at \(x=1.\)

Subproof 2: Consider \( x \in (0,2).\) Following a similar argument to Subproof 1, we can conclude that \(f(x)\) \(f(1).\)

____________

c) \(\;f\) has at \(x=-1.\)

Subproof 3: Clearly, \(f\) is an function.

Thus, it follows from the previous question in this quiz that \(f(x)\) \(f(-1)\).

____________

d) There are no other local extrema apart from those found in parts (a)-(c).

Subproof 4: In parts (a)-(c), we have identified all the local extrema in the domain \(x \in (-2,2).\)

For \( x \geq 2,\; f(x)=||x|-1|-1=\) .

On this domain, if \(x_1<x_2,\) then, subtracting 2 from both sides, we have \(f(x_1)<f(x_2).\) This shows that \(f\) is , and therefore has no local extrema for \(x \geq 2.\)

We can proceed in a similar way for \( x \leq -2\) (or use the odd/even property again) to deduce that there are no local extrema, in this case, either.

____________

You will notice that we have completed an investigation into the local extrema of a function without any differentiation.

The next question asks: could we have used differentiation to locate the local extrema for this function?

Referring to the same function \(f\) defined above, let us investigate if \(f\) is differentiable at its points of local extrema.

i) Consider \(F(x)=\frac{f(x)-f(c)}{x-c}.\)

Fill in the blanks in the table below with numbers.

 | \(\lim_{x \to c^-}F(x)\) | \(\lim_{x \to c^+}F(x)\)
\(c=0\) |  |
\(c=1\) |  |
\(c=-1\) |  |

ii) Since the left and right derivatives are ,
\(\; f\) is  at \(x=0,-1,1.\)

This question concerns the Ratio Lemma which we needed to study Taylor's Series. First, complete the blanks in the following proof.

Ratio Lemma: Let \(a_0,a_1,a_2, \ldots\) be a sequence of positive numbers. Suppose \(0<l<1\) and \(\frac{a_{n+1}}{a_n} \leq l\) for all \(n\in\mathbb{N}.\) Then \((a_n) \to 0.\)

Proof:
Let \(S(n)\) be the statement "\(a_n\) \( l^{n}a_0\)"  (\(n\in\mathbb{N}\)). If we can show that this statement is true then taking \(n\to \infty\) will show \(a_n \to 0.\)

We will prove this statement by induction.

1) Clearly, when \(0<l<1,\) we have \(\frac{a_1}{a_0} \leq l\) and so \(a_1 \leq\) . Hence, \(S(1)\) is true.

2) For an arbitrary \(k\in\mathbb{N}\), suppose that \(S(k)\) is true, meaning that \(a_k \leq\) .

3) Combining this with the assumption that \(\frac{a_{k+1}}{l} \leq a_k\), we have \(\frac{a_{k+1}}{l} \leq\) .

4) Consequently, \(a_{k+1} \leq\) .

5) Hence, we conclude that \(S(k)\implies S(k+1)\).

6) Since \(S(1)\) is true, we deduce that \(S(n)\) is true for all \(n\in\mathbb{N}.\) This completes the induction.

7) We now know that \(a_n \leq l^{n}a_0\) for all \(n,\) where \(l^n\) converges to and \(a_n \) is positive.

8) We therefore have \(0<a_n \leq l^{n}a_0\).
Letting \(n\to\infty\) and applying the , we conclude that \(a_n \to 0.\)

________

Further questions

a) Which step of the proof sets out the inductive hypothesis?

b) From the Ratio Lemma, we can deduce the following:

Ratio Lemma version 2: Let \(a_0,a_1,a_2, \dots\) be a sequence of positive numbers. Suppose \(0<l<1\) and \(\frac{a_{n+1}}{a_n} \leq l\) eventually. Then \((a_n) \to 0.\)

How might one deduce this result from the Ratio Lemma?

c) To which of the following sequences can we apply the Ratio Lemma (either version) to deduce that they converge to zero?

Let's prove this version of the sign-preservation lemma:

If \(f:A \to \mathbb{R}\) is continuous at \(c \in A\) and \(f(c) > 0,\) then \(\exists \delta > 0 \) such that \(\forall x \in (c-\delta, c+\delta)\), we have \(f(x) > 0.\)

Proof:

1) Since \(f\) is continuous at \(c, \forall \epsilon > 0, \exists \delta > 0\) such that

\(|x-c|< \delta \implies\) .

2) This means that \(< f(x) < \epsilon + f(c)\).

3) In particular, taking the left side of the above inequality, and choosing \(\epsilon=\) ?, the lemma follows.

_______________

Questions

a) Fill in the blanks in the above proof.

b) In step 3 of the proof, which of the following values could \(\epsilon\) take?

c) Without reproducing the proof above, we can deduce the following corollaries via a simple substitution.

Corollary 1: If \(f: A \to \mathbb{R}\) is continuous at \(c \in A\) and \(f(c) < 0,\) then \(\exists \delta > 0\) such that \(\forall x \in (c-\delta, c+\delta),\) we have \(f(x)<0.\)

Proof: Apply the sign-preservation lemma with \(g(x)=\) .

Corollary 2: If \(f: A \to \mathbb{R}\) is continuous at \(c \in A\) and \(f(c) < k,\) for some \(k \in \mathbb{R},\) then \(\exists \delta > 0\) such that \(\forall x \in (c-\delta, c+\delta),\) we have \(f(x)<k.\)

Proof: Apply the sign-preservation lemma with \(h_{1}(x)=\) or apply Corollary 1 with \(h_{2}(x)=\) .

Proof by induction

These questions give some examples of proof by induction.

We can ask students to focus on some of the algebraic steps, online, so that they can practice this particular aspect of induction before they are asked to create a whole proof for themselves.

Notes:
1. Many students cannot manipulate expressions such as \( (n+2)!-(n+1)! \) successfully, in which case trying to use this in an induction proof looks hopeless! By asking this separately, in advance, students can come to a proof later much better prepared.
2. Many students think \(P(n)\) is the value of the sum of the series, not the complete statement being proved. Asking the students to just state \(P(n+1)\) has proved to be a valuable question.

## Fill in the gaps

Another option is to have students fill in the gaps in proofs.

These could form part of a structured set of "faded worked examples" where student progressively take more responsibility for completing the proof so that, ultimately, they write the whole proof themselves. Faded worked examples allow increasing difficulty to be passed on to students, and avoids throwing them in at the deep end.