Mathematical Food for Thought


			Mathematical Food for Thought

google
yahoo
bing

About
Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

Meta
- Register
- Log in
- Valid XHTML
- XFN
- WordPress

Credits
- Design by Stacee Leung
- Coded by Daynah Nguyen
- Powered by Wordpress

Exponents Away. Topic: Algebra/Calculus. Level: AIME/Olympiad.	November 30th, 2006
Problem: (Problem-Solving Through Problems – 6.5.12) Suppose is a nonnegative integer and $f_n(x) = c_0e^{r_0x}+c_1e^{r_1x}+\cdots+c_ne^{r_nx}$ , where and are real numbers. Prove that if has more than zeros in $\mathbb{R}$ , then $f(x) \equiv 0$ . Solution: First, we add the claim that can occur for at most distinct . We proceed by induction. For , we have $f_0(x) = c_0e^{r_0x}$ which we know is not zero unless , so if it has a root it must be identically . It also takes the value at most once because it is monotonic. Now suppose both hypotheses are true for some nonnegative integer . We want to show that $f_{k+1}(x) = c_0e^{r_0x}+c_1e^{r_1x}+\cdots+c_ke^{r_kx}+c_{k+1}e^{r_{k+1}x}$ has at most zeros (except when for all ) and takes the value at most times. If $c_{k+1} = 0$ , we apply the inductive hypothesis and it is trivially true, so assume $c_{k+1} \neq 0$ . From $f_{k+1}(x) = 0$ , we get $c_0e^{r_0x}+c_1e^{r_1x}+\cdots+c_ke^{r_kx} = -c_{k+1}e^{r_{k+1}x}$ . Letting $b_i = -\frac{c_i}{c_{k+1}}$ and $q_i = r_i-r_{k+1}$ for $i = 0, 1, \ldots, k$ , we obtain $b_0e^{r_0x}+b_1e^{r_1x}+\cdots+b_ke^{r_kx} = 1$ . By our inductive hypothesis, we know this occurs at most times, proving that $f_{k+1}$ has at most zeros or is identically . Now we want to show that $f_{k+1}(x) = 1$ at most times. Suppose $f_{k+1}(x) = 1$ for $x_1 < x_2 < \ldots < x_m$ for . Then, by Rolle’s Theorem, we have $f_{k+1}^{\prime}(x) = c_0r_0e^{r_0x}+c_1r_1e^{r_1x}+\cdots+c_kr_ke^{r_kx}+c_{k+1}r_{k+1}e^{r_{k+1}x} = 0$ between each consecutive pair of ’s, giving us pairs. But by what we just proved for $f_{k+1}$ having at most zeros, we know $f_{k+1}^{\prime}(x) = 0$ at most times, since $f_{k+1}^{\prime}$ is in the same family of functions. Hence $f_{k+1}(x) = 1$ for at most distinct , completing the induction. Therefore, we conclude that has at most zeros or is identically . ——————– Comment: A pretty tough problem, took a couple of looks at smaller cases to determine the method with which to solve it. The key is looking for the inductive step, somehow reducing the case to the case. Adding in the extra condition might not have been necessary but it made it easier to move from case to case. Here’s a “flow chart” of what proves what. for at most values or is identically –> for at most values –> $f_{k+1}(x) = 0$ for at most values or is identically –> $f_{k+1}(x) = 1$ for at most values. ——————– Practice Problem: Show that cannot have more than one zero in , regardless of the value of . Posted in AIME, Algebra, Calculus, Olympiad \|\| No Comments »
Balance Those p’s. Topic: Algebra/Polynomials/S&S. Level: Olympiad.	November 29th, 2006
Problem: (Stanford Putnam Practice) A finite sequence $a_1, a_2, \ldots, a_n$ is called -balanced if any sum of the form $a_k+a_{k+p}+a_{k+2p}+\cdots$ is the same for $k = 1, 2, \ldots, p$ . Prove that if a sequence with members is -balanced for , then all its members are equal to zero. Solution: Let $P(x) = a_{50}x^{49}+a_{49}x^{48}+\cdots+a_2x+a_1$ . Recall the strategy of isolating certain terms in a polynomial. Denoting $\omega_p$ by the th root of unity, we have $\displaystyle a_1+a_{1+p}+a_{1+2p}+\cdots = \frac{1}{p} \sum_{i=0}^{p-1} P(\omega_p^i)$ because all of the terms will cancel out by the identity $1+\omega_p+\omega_p^2+\cdots+\omega_p^{p-1} = 0$ except for the terms in which the power of the exponent is divisible by , in which case $\omega_p^p = 1$ . Similarly, using the polynomials $xP(x), x^2P(x), \ldots, x^{p-1}P(x)$ we obtain $\displaystyle a_k+a_{k+p}+a_{k+2p}+\cdots = \frac{1}{p} \sum_{i=0}^{p-1} \omega_p^{i(p+1-k)}P(\omega_p^i)$ from $x^{p+1-k}P(x)$ and $k = 2, 3, \ldots, p$ . Hence we have a system of equations in the variables $P(1), P(\omega_p), \ldots, P(\omega_p^{p-1})$ . But if we have a system of equations for , we have a total of equations. Since the only repeated value in the polynomial was and it showed up times, once for each prime, there are distinct points on the polynomial that we now know. However, since a polynomial of degree is defined by at most points, it must be the zero polynomial, which means $a_1 = a_2 = \cdots = a_{50} = 0$ , as desired. QED. ——————– Comment: This is an example of generating functions showing up when you least expect it, well not exactly, but it was cool anyway. The proof above is not completely rigorous because we would need to show that a polynomial of degree actually cannot pass through all of the points, but it’s almost there. ——————– Practice Problem: Let denote the number of ways you can partition into parts. Show that $\displaystyle \sum_{k=1}^n p(n, k) = p(2n, n)$ . Also show that the number of ways can be partitioned into unequal parts is equal to the number of ways can be partitioned into odd parts. Posted in Algebra, Olympiad, Polynomials, Sequences & Series \|\| No Comments »
Divides Both! Topic: NT/S&S. Level: AIME.	November 28th, 2006
Problem: (Stanford Putnam Practice) Let and $a_{n+1} = a_n^2+1$ for $n \ge 0$ . Find $\gcd(a_{2004},a_{999})$ . Solution: Re-label starting with , instead. We will prove a much stronger statement, that, $\gcd(a_m, a_k) = a_{gcd(m,k)}$ for $m, k \neq 0$ . First, we will show a lemma that if for positive integers then $a_{r+s} \equiv a_s \pmod{q}$ for $s \ge 0$ . This is trivial by induction, since $a_r \equiv a_0 \pmod{q}$ , $a_{r+s+1} \equiv a_{r+s}^2+1 \pmod{q}$ , and $a_{s+1} \equiv a_s^2+1 \pmod{q}$ . We will prove the final result by induction as well, on $\max(m,k)$ . When this is , we clearly have $(a_1, a_1) = 1 = a_{\gcd(1,1)}$ . Assume the property is true for $\max(m,k) \le p$ . Now suppose $\beta$ divides $\gcd(a_m,a_{p+1})$ with . We must have $a_m \equiv a_{p+1} \equiv 0 \pmod{\beta}$ . But then by the lemma above we have $\beta \| a_m \Rightarrow a_{p+1} \equiv a_{p+1-m} \equiv 0 \pmod{\beta}$ . So then $\gcd(a_m,a_{p+1}) = \gcd(a_m,a_{p+1-m})$ with $p+1-m \le p$ . But by our inductive hypothesis, we know that $\gcd(a_m,a_{p+1-m}) = a_{\gcd(m,p+1-m)} = a_{\gcd(m,p+1)} = \gcd(a_m,a_{p+1})$ , as desired. Shifting the indices in the problem statement, we have $\gcd(a_{2005}, a_{1000}) = a_{\gcd(2005,1000)} = a_5 = 677$ . QED. ——————– Comment: Pretty classic as far as GCD of terms in a sequence go. It follows a similar property that the Fibonnacci sequence also has. Instead of using induction on the last step, another option was to invoke Euclid’s Algorithm to arrive at $\gcd(m,p+1)$ but that didn’t seem quite as fulfilling. ——————– Practice Problem: (Stanford Putnam Practice) Define a sequence $\{a_i\}$ by and $a_{i+1} = 3^{a_i}$ for $i \ge 1$ . Which integers between and occur as the last two digits of infinitely many ? Posted in AIME, Number Theory, Sequences & Series \|\| No Comments »
To Converge Or Not To Converge. Topic: Real Analysis/S&S.	November 27th, 2006
Problem: (Stanford Math 51H, Cauchy Root Test) Suppose there exists a $\lambda \in (0,1)$ and an integer $N \ge 1$ such that $\|a_n\|^{\frac{1}{n}} \le \lambda$ for all $n \ge N$ . Prove that $\displaystyle \sum_{n=1}^{\infty} a_n$ converges. Solution: Well let’s just discard $\displaystyle \sum_{n=1}^{N-1} a_n$ because it is finite and obviously converges. It remains to show that $\displaystyle \sum_{n=N}^{\infty} a_n$ converges. But then we have $\|a_n\|^{\frac{1}{n}} \le \lambda \Rightarrow \|a_n\| \le \lambda^n$ . So $\displaystyle \sum_{n=N}^{\infty} a_n \le \sum_{n=N}^{\infty} \|a_n\| \le \sum_{n=N}^{\infty} \lambda^n$ . The last summation, however, is a geometric series with common ratio $0 < \lambda < 1$ , so it converges. Hence our sum does as well. QED. ——————– Comment: The root test is, in effect, a comparison to a geometric series. The hypothesis is that we can bound by a geometric series for all large , implying convergence. ——————– Practice Problem: (Stanford Math 51H) Discuss the convergence of $\displaystyle \sum_{n=1}^{\infty} \frac{\sin{\frac{1}{n}}}{n}$ . Posted in Real Analysis, Sequences & Series \|\| 3 Comments »
Stirling Silver. Topic: Calculus.	November 25th, 2006
Problem: Evaluate $\displaystyle \lim_{n \rightarrow \infty} \frac{k^n \cdot n!}{n^n}$ where is an arbitrary positive real number. Solution: Well in its current form the limit does not look very fun, so let’s take the natural log of it. $\displaystyle \ln{L_k} = \lim_{n \rightarrow \infty} \left(n \ln{k}+\sum_{i=1}^n \ln{i}-n\ln{n}\right)$ where is the limit in question. Let’s bound the summation term on the RHS using integrals. We see that $\displaystyle \int_1^n \ln{x} dx \le \sum_{i=1}^n \ln{i} \le \int_1^n \ln{x}dx + \ln{n}$ $\displaystyle n\ln{n}-n \le \sum_{i=1}^n \ln{i} \le n\ln{n}-n+\ln{n}$ because $\displaystyle \int \ln{x} dx = x\ln{x}-x$ . Plugging this back into the equation, we get $\displaystyle \lim_{n \rightarrow \infty} n(\ln{k}-1) \le \ln{L_k} \le \lim_{n \rightarrow \infty} n(\ln{k}-1)+\ln{n}$ . For , the coefficient of the term is negative and it dominates the $\ln{n}$ term, so as $n \rightarrow \infty$ both the upper and lower bounds approach $- \infty$ , hence $\ln{L_k} \rightarrow -\infty \Rightarrow L_k \rightarrow 0$ . For , the coefficient on the term is positive, so both the upper and lower bounds approach $\infty$ so $\ln{L_k} \rightarrow \infty \Rightarrow L_k \rightarrow \infty$ . Now for the trickier case . Consider a midpoint approximation of the area under the curve $\ln{x}$ from $\frac{1}{2}$ to $n+\frac{1}{2}$ . Since $\ln{x}$ is concave, the midpoint approximation will be larger than the integral (draw a picture to see this). So $\displaystyle \int_{\frac{1}{2}}^{n+\frac{1}{2}} \ln{x}dx \le \sum_{i=1}^n \ln{i}$ . But the LHS turns out to be $\left(n+\frac{1}{2}\right)\ln{\left(n+\frac{1}{2}\right)}-\left(n+\frac{1}{2}\right)-\frac{1}{2}\ln{\frac{1}{2}}+\frac{1}{2}$ which we can bound below by $n\ln{n}+\frac{1}{2}\ln{n}-n+C$ for some arbitrary constant . Then $\displaystyle \sum_{i=1}^n \ln{i} \ge n\ln{n}+\frac{1}{2}\ln{n}-n+C$ . Plugging back into our original expression for $\ln{L_k}$ , we obtain $\ln{L_e} \ge \lim_{n\rightarrow \infty} (n+n\ln{n}+\frac{1}{2}\ln{n}-n+C-n\ln{n}) = \lim_{n\rightarrow \infty} (\frac{1}{2}\ln{n}+C) = \infty$ so $L_e \rightarrow \infty$ as well. Hence if , the limit converges to zero and if $k \ge e$ the limit diverges to $\infty$ . QED. ——————– Comment: This limit it very interesting because it gives us an idea about Stirling’s approximation. In fact, from the last inequality, we see that $L_e \sim \sqrt{n}$ and we have $n! \sim \left(\frac{n}{e}\right)^n \cdot \sqrt{n}$ . A very good approximation is $n! \approx \sqrt{\pi \cdot \left(2n+\frac{1}{3}\right)} \cdot \left(\frac{n}{e}\right)^n$ . Posted in Calculus \|\| No Comments »

free web counters