Wikipedia:Reference desk/Archives/Mathematics/2008 December 6

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 6

Inequality

Hello. I need to prove the following inequality using induction on n. $13+4t^{2}+2n+{\frac {2}{n}}\leq {\frac {t^{2}}{n}}+2tn+8t+{\frac {2t}{n}}$. It is known that $3\leq t\leq {\frac {n}{2}}$. The base case when n=6 and hence t=3 is trivial. After that I am stuck. I can't find a way to use the induction hypothesis for n to prove the inequality for n+1. I'll be grateful for any help.--Shahab (talk) 14:02, 6 December 2008 (UTC)

Presumably n is always positive? In that case, you can multiply through by it and then rearrange the inequality to put everything on one side giving you a quadratic in n. I don't know if it will help, but that would be the first thing I would try. --Tango (talk) 14:30, 6 December 2008 (UTC)

I don't know about doing this by induction, but here's a solution. Move everything over to the left side. You need to prove that the values of the function of t you get are negative or zero. It's a quadratic function at² + bt + c, with positive a, and attaining its minimum at -b/2a, which you can prove is ≥ n/2. Thus, on the interval 3 ≤ t ≤ n/2, the function is decreasing, and hence its maximum is attained at t = 3. Therefore, it's enough to check your inequality for t = 3. This turns out to be a quadratic inequality in n which is true for n ≥ 6. 67.150.244.6 (talk) 14:40, 6 December 2008 (UTC)

Thanks for the solution 67.150.244.6. But I am still curious to know whether it is possible to solve the problem by induction. It occurs in my textbook which uses this inequality in a proof followed by a comment that straightforward induction proves it. Anyway, cheers--Shahab (talk) 16:08, 6 December 2008 (UTC)

If you do what I suggested and take everything over to one side and multiply through by n, you get: $13n+4t^{2}n+2n^{2}+2-t^{2}-2tn^{2}-8tn-2t\leq 0$. If you take just the LHS and replace n by n+1 you get: $13(n+1)+4t^{2}(n+1)+2(n+1)^{2}+2-t^{2}-2t(n+1)^{2}-8t(n+1)-2t=(13n+4t^{2}n+2n^{2}+2-t^{2}-2tn^{2}-8tn-2t)+(13+4t^{2}+4n+2-4tn-2t-8t)$. The first part you already know is less than or equal to zero, so you just need to show the 2nd part is. That part simplifies to: $13+4t^{2}+4n+2-4tn-2t-8t=4t^{2}-(4n+10)t+13\leq 4t^{2}-(4(2t)+10)t+13=4t^{2}-8t^{2}-10t+13=-4t^{2}-10t+13$. And that is less than zero for t>3 (in fact, for t>1). --Tango (talk) 16:32, 6 December 2008 (UTC)

Thanks. I couldn't have asked for a better explanation.--Shahab (talk) 16:38, 6 December 2008 (UTC)

That doesn't quite work, unfortunately. To use the induction hypothesis, you need $t\leq {\frac {n}{2}}$, but all you have is $t\leq {\frac {n+1}{2}}$. Algebraist 16:41, 6 December 2008 (UTC)

Moreover what's up with $13+4t^{2}+4n+2-4tn-2t-8t=4t^{2}-(4n+10)t+13$. I guess 67.150.244.6 method is best.--Shahab (talk) 16:52, 6 December 2008 (UTC)

You mean why does 13+2=13? That's a good question. My bad arithmetic doesn't change the answer, though. Algebraist's point that the constraint we're given is a function of n, which I completely failed to account for, is a more serious issue. I certainly agree that the non-induction approach is better, I was just trying to find an induction approach since that's what the OP wanted. --Tango (talk) 17:14, 6 December 2008 (UTC)

Here's an alternative to the end of the previous solution if you don't feel like proving that -b/2a ≥ n/2. The function at² + bt + c is concave upward, and therefore attains its maximum on the interval 3 ≤ t ≤ n/2 at one of the endpoints. Therefore it's enough to check the inequality for t = 3 and t = n/2. 67.150.254.10 (talk) 05:30, 7 December 2008 (UTC)

simple productivity calculation

Say a person can make 1 widget every 20 seconds. New technology is installed that allows her to make 1 widget every 15 seconds. What can one say is the productivity gain in percentage points due to the new technology, how does one calculate that figure?

I am trying to do similar calculations for a report and I am math-illiterate sometimes. Thanks for any help. -- 12.181.197.100 (talk) 16:55, 6 December 2008 (UTC)

I think you want to convert it from seconds per widget to widgets per second (or minute, is easier). 3 widgets per minute going to 4 widgets per minute is a 33% increase in productivity. --Tango (talk) 17:16, 6 December 2008 (UTC)

is (20/15 - 1) * 100 a correct way to calculate this? the answers seem right. —Preceding unsigned comment added by 12.181.197.100 (talk) 18:10, 6 December 2008 (UTC)

Yes, that's correct. That's (widgets per second after-widgets per second before)/(widgets per second before)*100%. --Tango (talk) 18:20, 6 December 2008 (UTC)

Also note that the numbers aren't reversible. That is, if productivity dropped from 4 per minute to 3 per minute, that would be a 25% reduction, using 4 as a base. StuRat (talk) 04:48, 7 December 2008 (UTC)

half functions

I have an idea that functions could be performed in two equivalent steps, $f(x)=g(g(x))$ where g(x) is the half function of f(x). Is there such a concept in Mathematics? Is there a way to work out what g is from f, even numerically?

For example if $f(x)=x^{2}$ then $g(x)=x^{\sqrt {2}}$ or $f(x)=3x$ gives $g(x)=x{\sqrt {3}}$. What would the half function of the logarithm be? Graeme Bartlett (talk) 22:07, 6 December 2008 (UTC)

Functional square root. Algebraist 22:17, 6 December 2008 (UTC)

Thanks! - that's what I want, Functional equation#Solving functional equations gives a clue. Graeme Bartlett (talk) 07:11, 8 December 2008 (UTC)

The theory you need depends to a great extent on what object is the map \phi you have in mind. If it is a continuous or differentiable mapping of the real line into itself (or on a differentiable manifold into itself), you may even be thinking to some collection $\phi ^{t}$ with real parameters t , generalizing the n fold composition of $\phi$: then I'd say that what you have in mind is to embed a discrete (semi-)dynamical system into a continuous one. This problem can be treated; one way is to look for $\phi ^{t}$ as the flow of some ODE: $\scriptstyle \partial _{t}\phi ^{t}(x)=F(\phi ^{t}(x))$ with $\phi ^{0}(x)=x$: then you seek for a suitable field F. If your $\phi$ is a square matrix, or even a linear operator on a Banach space, then you are in the realm of functional calculus and spectral theory (one important example of square root of a very simple operator is the Fourier transform). And so on: every different type of objects springs a whole theory and a class of methods--PMajer (talk) 14:22, 10 December 2008 (UTC)

Large Counterexamples and Proof by Induction

I am teaching my kids about proofs using induction and I am trying to get them to understand that just because a statement is true for a first few numbers or the pattern is obvious for a first few terms does NOT automatically tell us that the statement is true for all numbers or that the pattern holds for ALL terms. One of the best examples, which I showed, was showing that $n^{2}-n+41$ is prime if n is a natural number between 1 and 40. But for n=41, the statement is false. This is exactly the reason why we do proofs in Math and everything must be proven rigorously. My question is, do you guys know of any other similar examples that I can enlighten my kids with, something where the pattern looks obvious but is wrong for all integers and therefore is misleading?

Another request is about a statement which is true for all integers so that I can do a decreasing proof by induction meaning that first I show that the statement S is true for n=-1 and then show that if it is true for n=k, it will be true for n=k-1. Something only with negative integers only, I think, is easy to come up with. I can just take something true for all natural numbers and then plug in -n. How about something that is true for all positive and negative integers so that I can do n=k true implies n=k+1 true and then n=k true implies n=k-1 also true. Something even better would be something that is true for all integers except for a finite number of integers around zero like true for all integers less than -3 and all integers larger than 3. Thanks!-Looking for Wisdom and Insight! (talk) 23:31, 6 December 2008 (UTC)

The traditional example is to put n points on the circumference of a circle, draw all lines connecting them (with the points chosen so that no three lines meet at a point) and count the regions the circle is divided into. Algebraist 23:34, 6 December 2008 (UTC)

OK, let's see:

$2\times 2=2+2\,$

$1\times 2\times 3=1+2+3\,$

$3\times 1.5=3+1.5.\,$

Therefore multiplication is the same thing as addition. Michael Hardy (talk) 06:11, 7 December 2008 (UTC)

Here's an example from Pólya (which I found in Calculus by Apostol):

Given any collection of n blonde girls, if one of them has blue eyes, then they all do.

Proof by induction on n: This is clearly true for n = 1. Assuming it is true for all n < p, we prove it for p. Let S be a collection of p blonde girls, one of whom, s, has blue eyes. Then S can be written as a union of two sets S₁ and S₂ with fewer elements than S, each containing s. Applying the induction hypothesis to S₁ and S₂, we conclude that all the girls in S₁ and S₂, and hence all those in S, have blue eyes. This proves the statement is true for p. Hence the statement is true by induction.

Corollary: All blonde girls have blue eyes.

Proof: Consider the collection of all blonde girls. One of them has blue eyes, hence they all do.

There's a freely available 36-page book on mathematical induction by A. Shen, who's a terrific author, but it's in Russian. It's intended for grades 7-11. Here's the link: [1] The same website also lists a book on induction in geometry, but I haven't looked at it. 67.150.254.10 (talk) 06:20, 7 December 2008 (UTC)

All horses are the same color. Algebraist 06:22, 7 December 2008 (UTC)

The best one I know is that the coefficients of the factorization of $x^{n}-1$ are all unity [for example, $x^{3}-1=(x^{2}+x+1)\cdot (x-1)$]. This is true for n=1,2,3,...,104 but false for 105. HTH. Robinh (talk) 22:51, 7 December 2008 (UTC)

I think there are clearly two different things that have been talked about here:

1. Proofs by induction that contain subtle errors.

2. Things that are true for the first several integers, but not for all integers. These examples (like n² - n + 41) have nothing at all to do with mathematical induction. 67.150.244.99 (talk) 23:37, 7 December 2008 (UTC)

How about the primality of Fermat numbers? Fermat guessed that all numbers of the form $2^{2^{n}}+1$ are prime, but in fact this seems to be true only for n = 0, …, 4. It's not true for 5 ≤ n ≤ 32, and it is conjectured that in fact it's never true except for 0 ≤ n ≤ 4. —Bkell (talk) 15:35, 8 December 2008 (UTC)

The smallest counterexample to π(x) ≤ li(x) (where π is the prime counting function and li is the logarithmic integral function), while not rigorously known, is estimated to have an insane value of about 1.397 × 10³¹⁶. See Skewes' number. — Emil J. 16:04, 8 December 2008 (UTC)

See also [2], [3] and for some humour [4]. PrimeHunter (talk) 02:21, 9 December 2008 (UTC)

This is a bit different from what you were asking for, but if your kids are tempted to resort to computers or calculators for testing conjectures, you might want to have them try iterating the function $f:[0,1]\to [0,1]$, $f(x)=|2x-1|$ (a variant of the tent map) on a calculator. Starting from any floating-point number (or, more generally, dyadic rational) on the unit interval, the sequence will quickly reach the fixed point 1. However, it's easy to show that this behavior is far from universal: there's another fixed point at 1/3, and indeed any non-dyadic rational starting point will lead either there or to a repeating cycle within the unit interval. Furthermore, for irrational starting points, which make up the almost all of the real numbers, the sequence is chaotic and will never repeat. —Ilmari Karonen (talk) 05:08, 9 December 2008 (UTC)

This is elementary: if you cut the three dimensional space with n = 0, 1, 2, 3 plane cuttings in a generic position, you get respectively 1, 2, 4, 8 pieces; but the first obvious conjecture of getting in general $2^{n}$ pieces falls with n=4, for then one gets 15. The correct number of pieces in general is $\scriptstyle {n \choose 0}+{n \choose 1}+{n \choose 2}+{n \choose 3}$.--PMajer (talk) 16:29, 9 December 2008 (UTC)

The Strong Law of Small Numbers is relevant here. Algebraist 16:36, 9 December 2008 (UTC)

Except that this is far from a coincidence. The formula 2ⁿ would be valid for n hyperplanes in an m-dimensional space, with n ≤ m. Still, I agree with PMajer that there would be a danger of overgeneralization. It's funny, because here the prudent thing to do to test the assumption can either be to make n larger or to make m smaller. 67.150.245.29 (talk) 17:07, 9 December 2008 (UTC)