Induction questions (1 Viewer)

Jonothancroller · Oct 4, 2015

Here are the questions: http://m.imgur.com/scXruJa

I'm not really sure how to start on the questions in 17, and I can't do 18.

leehuan · Oct 4, 2015

17:
(a) Prove that the formula is true for T1 and T2 (the sequence generator uses two terms), and then in the inductive step proving T(k+1)=3Tk-2T(k-1) assume all cases are true up to k, so you can sub in the formula for Tk and T(k-1). Then it's algebra.

(c) is a very typical induction proof for the nth term of the Fibonacci sequence. Eddie Woo has a video on it.

InteGrand · Oct 4, 2015

Jonothancroller said:
Here are the questions: http://m.imgur.com/scXruJa

I'm not really sure how to start on the questions in 17, and I can't do 18.

$18. (a) $\textsl{\underline{Aim}: Prove by induction that}$ $\frac{a_1+a_2+\cdots + a_{2^n}}{2^n}\geq (a_1a_2...a_{2^n})^{\frac{1}{2^{n}}}$\textsl{ for all} $n\in \mathbb{Z}^+$.$

$\underline{\textbf{Proof.}}$$$

$\underline{Step 1: Base Case}$

$When $n=1$, $2^n=2$, so the statement to prove is that $\frac{a_1+a_2}{2}\geq \sqrt{a_1a_2}$.$

$To prove this, note that $\left(\sqrt{a_1}-\sqrt{a_2}\right)^2\geq 0$ (since a square is always non-negative).$

$Therefore, expanding this out gives $a_1-2\sqrt{a_1}\sqrt{a_2}+a_2\geq 0$$

$\Rightarrow a_1 + a_2 \geq 2\sqrt{a_1a_2}$

$$\Rightarrow \frac{a_1 + a_2}{2} \geq \sqrt{a_1a_2}$, so the statement is true for $n=1$.$

$\underline{Step 2: Induction Step}$

$Assume that the statement is true for $n=j$, where $j$ is a positive integer. That is, assume that for any arbitrary $2^j$ positive numbers $a_1,a_2,...,a_{2^j}$.$

$$\frac{a_1+a_2+\cdots + a_{2^j}}{2^j}\geq (a_1a_2...a_{2^j})^{\frac{1}{2^{j}}}$ (*)$ .

$Then we need to prove that the statement is true for $n=j+1$, i.e. that$

$$\frac{a_1+a_2+\cdots + a_{2^{j+1}}}{2^{j+1}}\geq (a_1a_2...a_{2^{j+1}})^{\frac{1}{2^{j+1}}}$ (**)$

$\underline{Proof.}$$$

$Note that $2^{j+1}=2\times 2^j=2^j+2^j$, so the $LHS$ is$

$$LHS\text{ of (**)}=\frac{(a_1+a_2+\cdots + a_{2^j})+(a_{2^{j}+1}+a_{2^j+2}+\cdots + a_{2^{j+1}})}{2\times 2^{j}}$ (where each bracketed expression has $2^j$ terms)$

$$=\frac{\frac{a_1+a_2+\cdots + a_{2^j}}{2^j}+\frac{a_{2^{j}+1}+a_{2^j+2}+\cdots + a_{2^{j+1}}}{2^{j}}}{2}$ (just an algebraic manipulation)$

$$=\frac{A+B}{2}$, where for brevity we have let$

$$A=\frac{a_1+a_2+\cdots + a_{2^j}}{2^j}$ and $B=\frac{a_{2^{j}+1}+a_{2^j+2}+\cdots + a_{2^{j+1}}}{2^{j}}$.$

$Now notice that $A$ and $B$ are both the arithmetic means of $2^j$ arbitrary positive numbers. By our inductive hypothesis (*), these are both greater than or equal to the geometric means, that is, by our assumption (*), we have$

$$A\geq (a_1a_2...a_{2^j})^{\frac{1}{2^{j}}}$ (1)$

$and$

$$B\geq (a_{2^j + 1}a_{2^j+ 2}...a_{2^{j+1}})^{\frac{1}{2^{j}}}$ (2)$ .

$Substituting these results into the $LHS$ equation we had above, and recalling from the base case that $\frac{A+B}{2}\geq \left( AB\right)^{\frac{1}{2}}$, yields$

$LHS\text{ of (**)}=\frac{A+B}{2}$

$\geq (AB)^{\frac{1}{2}}$

$$\geq \left[\left(a_1a_2...a_{2^j}\right)^{\frac{1}{2^{j}}} \times (a_{2^j + 1}a_{2^j+ 2}...a_{2^{j+1}})^{\frac{1}{2^{j}}}\right]^{\frac{1}{2}}$, by results (1) and (2)$

$=(a_1a_2...a_{2^j}a_{2^j + 1}a_{2^j+ 2}...a_{2^{j+1}})^{\frac{1}{2^{j+1}}}$, simplifying using index laws$

$$=RHS\text{ of (**)}$, as required.$

$\underline{Step 3: Conclusion}$

$It follows from Steps 1 and 2 by the Principle of Mathematical Induction that $\frac{a_1+a_2+\cdots + a_{2^n}}{2^n}\geq (a_1a_2...a_{2^n})^{\frac{1}{2^{n}}}$ for all $n\in \mathbb{Z}^+$.$

$18. (b) We have assumed that$

$$\frac{a_1+a_2+\cdots+a_{k-1}+a_k}{k}\geq \left(a_1 a_2...a_{k-1}a_k\right)^{\frac{1}{k}}$ ($\prime $)$

$for \emph{any} set of positive numbers $a_1,a_2,...,a_k$, where $k$ is an integer, $k\geq 2$.$

$Since this assumption holds for \emph{any} possible set of positive numbers $a_1,a_2,...,a_k$, it holds when we let $a_k=(a_1a_2...a_{k-1})^{\frac{1}{k-1}}$, since this is also a positive number. So substituting this into our assumption ($\prime$) yields$

$$\frac{a_1+a_2+\cdots+a_{k-1}+\underbrace{(a_1a_2...a_{k-1})^{\frac{1}{k-1}}}_{a_k}}{k}\geq \left(a_1 a_2...a_{k-1}\times \underbrace{(a_1a_2...a_{k-1})^{\frac{1}{k-1}}}_{a_k}\right)^{\frac{1}{k}}$ (just direct substitution)$

$$\Longleftrightarrow \frac{a_1+a_2+\cdots+a_{k-1}}{k}+\frac{(a_1a_2...a_{k-1})^{\frac{1}{k-1}}}{k}\geq \left((a_1a_2...a_{k-1})^{\frac{k}{k-1}} \right)^{\frac{1}{k}}$ (by doing the following simplification on the R.H.S.: $a_1a_2...a_{k-1} \times (a_1a_2...a_{k-1})^{\frac{1}{k-1}} = \left(a_1a_2...a_{k-1} \right)^{1+\frac{1}{k-1}} = \left(a_1a_2...a_{k-1} \right)^{\frac{k}{k-1}}$, using the index law $X^r \times X^s = X^{r+s}$)$

$$\Longleftrightarrow \frac{a_1+a_2+\cdots+a_{k-1}}{k}+\frac{(a_1a_2...a_{k-1})^{\frac{1}{k-1}}}{k}\geq \left(a_1a_2...a_{k-1}\right)^{\frac{1}{k-1}}$ (using this index law on the R.H.S.: $\left(X^{\frac{k}{k-1}}\right)^{\frac{1}{k}} = X^{\frac{k}{k-1}\times \frac{1}{k}}=X^{\frac{1}{k-1}}$)$

$$\Longleftrightarrow \frac{a_1+a_2+\cdots+a_{k-1}}{k}\geq \left(a_1a_2...a_{k-1}\right)^{\frac{1}{k-1}} -\frac{(a_1a_2...a_{k-1})^{\frac{1}{k-1}}}{k}$ (rearranging the previous inequality)$

$$\Longleftrightarrow \frac{a_1+a_2+\cdots+a_{k-1}}{k}\geq \left(1-\frac{1}{k} \right)\cdot \left(a_1a_2...a_{k-1}\right)^{\frac{1}{k-1}}$ (factorising the previous R.H.S.)$

$$\Longleftrightarrow \frac{a_1+a_2+\cdots+a_{k-1}}{k}\geq \left(\frac{k-1}{k} \right)\cdot \left(a_1a_2...a_{k-1}\right)^{\frac{1}{k-1}}$ (since $1-\frac{1}{k}=\frac{k-1}{k}$)$

$$\Longleftrightarrow \frac{a_1+a_2+\cdots+a_{k-1}}{k-1}\geq \left(a_1a_2...a_{k-1}\right)^{\frac{1}{k-1}}$ (cancelling the $k$'s from the denominators of both sides and moving the $k-1$ from the numerator of the R.H.S. to the denominator of the L.H.S.), which is precisely what we wanted to prove!$

$18. (c) From part (a), we know that the statement is true for any power of two, and from part (b), we know that the statement is true for any whole number less than a number that we know it is true for. Combining these, we can say the statement is true for any integer $N$, because we can always say it is true for some power of 2 that is larger than $N$, and then work our way down by part (b) until we get to it being true $N$ (this is just the Principle of Mathematical Induction, just a variant to the one you're used to $\ddot{\smile}$). \blacksquare$

Induction questions (1 Viewer)

Jonothancroller

Member

leehuan

Well-Known Member

InteGrand

Well-Known Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)