Proof by Induction?

**Isomorphism** · May 14th 2009, 05:12 AM

Originally Posted by Aquafina

ah that's really good! (yes 9 was a typo sorry)

how come only the upper boundary of n being odd is related to n > 3? i.e. with n^2 - 2n - 3 > 0

Also, how would you come up with these equations from scratch!? I get how I worked back from fardeen's work to get the case...

Thats why i called his inequalities ingenious!! I think getting it is an art

I was trying to bound it between squares of two consecutive numbers initially.. But I could not get it

**Aquafina** · May 14th 2009, 05:55 AM

sorry i took long to reply i didn't realise it went on to a new page...

hmm that's pretty clever, i'll PM fardeen to ask him for his suggestions.

Thanks

**pickslides** · May 15th 2009, 12:04 AM

some thoughts,

1. try the normal method for induction, show the theorm is true for n=1 (well in your case n=4 as n>3) is not a perfect square then assume n=m is not a perfect square and in turn prove n = m+1 is not a perfect square

for n = 4: $4^4+4^3+4^3+4^1+1=341$ not a perfect square!

assume n = m is not a perfect square

$m^4+m^3+m^3+m^1+1\neq k^2$

to help prove n = m + 1 is not a perfect square

$(m+1)^4+(m+1)^3+(m+1)^3+(m+1)^1+1\neq k^2$

you will have to expand this out, group like terms and in turn look at the case of n = m to make the appropriate substitutions. Sounds like a big job...

or

2. try the same with an equals sign i.e

$n^4+n^3+n^3+n^1+1\neq k^2+c$

where c is forcing the RHS not to be a perfect squrare. I cannot think of any type of value that would work for now. If one could be found then an argument for the squared values being knocked out could be valid.

**Aquafina** · May 15th 2009, 02:24 AM

when you said:

2. try the same with an equals sign i.e

did you mean "=" instead?

i'll try that method, do you have any starters on it that i can work through because im not 100% sure how to prove the m+1 case..

or do you have any ideas how to generate the inequalities fardeen used?

**Aquafina** · May 15th 2009, 05:51 AM

ok this is what i got so far... sorry i'm not sure how to insert the mathematical formulae like u did so i'll have to type it out with "^" and stuff lol...

ok expanding the (m+1) case I got:

m^4 + 5m^3 + 10m^2 + 10m + 5 ≠ k^2

I wasn't able to see how the 'm' case would help with this.. but i tried factorising it to:

(m^2 + 5)^2 + 5(m^3 + m -4) ≠ k^2

not sure if this has gotten me anywhere... some help please

**Aquafina** · May 15th 2009, 06:49 AM

something else I got with the "m+1" case was...

m^4 + 5m^3 + 10m^2 + 10m + 5 ≠ k^2

m^4 + 5m^3 + 10m^2 + 10m + 4 + 1 ≠ k^2

(m+1)(m+2)(m^2 + 2m + 2) + 1 ≠ k^2...

not sure if this is useful either, but perhaps the +1 might lead to somewhere in proving that it isnt a perfect square..?

**Media_Man** · May 15th 2009, 06:51 AM

Aquafina,

You queried as to where fardeen_gen's inequalities "came from." In more precise terms, you wanted to know how to derive these a priori. I would say that is a very difficult thing to do. Consider the even case,

$(n^{2}+\frac{n}{2})^{2}<\frac{n^{5}-1}{n-1}< (n^{2}+\frac{n}{2}+1)^{2}$ for all $n>3$ even

Expanding both sides, you can easily verify that this holds:

$n^4+n^3+\frac{1}{4}n^2 < n^4+n^3+n^2+n+1 < n^4+n^3+\frac{9}{4}n^2+n+1$

Subtracting,

$-(\frac{3}{4}n^2+n+1) < 0 < \frac{5}{4}n^2$

For positive values of $n$ , this is quite easily the case. So, verifying fardeen_gen's proof is straightforward. But if you are asking fardeen_gen to recreate the moment of inspiration from whence this inequality holds, I believe that is an unfair question, akin to asking a magician to reveal the secret behind a trick, or a master chef for a secret recipe. Perhaps fardeen_gen simply noticed a less than obvious pattern the rest of us didn't. You would have to ask fardeen_gen.

Perhaps this inspiration was achieved by looking at the greatest square less than $\frac{n^5-1}{n-1}$ , finding a formula to find this square for a given $n$ , and recognizing that this square and the one directly after it would always trap the value of your function between them.

Letting $f(n)=\frac{n^5-1}{n-1}$ , and $g(n)=\lfloor \sqrt{f(n)} \rfloor$ , $g(4,5,6,...)=18,27,39,52,68,85,105,126,150,...$ . In each case, $g(n)$ appears to equal $n^2+\lfloor \frac{n}{2} \rfloor$ and verifying this to always be the case would be relatively easy.

Whatever the inspiration, we must always respect a mathematician's ability to see order where others see only chaos. It is this respect, by the way, that keeps them active on this site to continue helping us mere mortals.

On another note, your original post never made mention of the possibility of n being negative, as this will require a different proof. If you truly want to find the root reason as to why n=3 appears to be the only integer satisfying your criteria, perhaps start a new thread asking, "Prove that $n=3$ is the only integer making $\frac{n^5-1}{n-1}$ a perfect square," as this new phrasing may inspire a different line of attack.

**Aquafina** · May 15th 2009, 08:23 AM

thanks for your help

i think i'll do that because it does seem to be an interesting question

**Media_Man** · May 15th 2009, 02:43 PM

After looking more closely, I realized that fardeen_gen's inequalities do prove the negative case as well. Consider:

Case I: n even:

$(n^{2}+\frac{n}{2})^{2}<\frac{n^{5}-1}{n-1}< (n^{2}+\frac{n}{2}+1)^{2}$

$-(\frac{3}{4}n^2+n+1) < 0 < \frac{5}{4}n^2$

This holds for all $n \neq 0$

Case II: n odd:

$(n^{2}+\frac{n-1}{2})^{2} < \frac{n^{5}-1}{n-1} < (n^{2}+\frac{n+1}{2})^{2}$

$-\left(\frac74 n^2 + \frac32 n + \frac34\right) < 0 <\frac{n^2 - 2n - 3}{4}$

This holds for all $n<-1$ and $n>3$ (leaving exceptions $n=-1,1,3$ )

Combining these two cases, the inequalities hold for all integers $n \in \mathbb{Z}$ - positive and negative - except for : $n=-1,0,1,3$ . Testing each of these by trial, $n=-1,0,3$ return integers, and $n=1$ does not.

Therefore, (-1,1) (0,1) and (3,11) are the only integer solutions to the function $f(n)=\sqrt{\frac{n^5-1}{n-1}}$

**Deadstar** · May 18th 2009, 05:28 AM

Just thought i'd throw my hat in the ring and show aquafina how to figure out bounds like fardeens.

Take the case of n even. Pug n=4 into the equation $n^4 + n^3 + n^2 + n + 1$ and you get 341 which is not a perfect square, hence there exist a perfect squares on either side of it of the form $x^2$ and $(x+1)^2$ .

The nearest perfect square below 341 is 324 which is $18^2$ . So we need a formula such that 'x' = 18 and hence $(x)^2 = 324$ . ('x' is going to be a formula involving n).

Note that since the leading coefficient of $n^4$ in your formula is 1 we need an $n^2$ in ours so that $(n^2)^2 = n^4$ . So we have the start of our formula for 'x'.

Now if we plug 4 into our $n^2$ term we get 16. Since we need 18 we need another term such that when you plug 4 into it you get +2. $\frac{n}{2}$ is the simplest such term. Put it together and you get $'x' = n^2 + \frac{n}{2}$ and hence $(n^2 + \frac{n}{2})^2$ is a perfect square less than $(n^4 + n^3 + n^2 + n + 1$ for even n.
To get the upper bound simply add 1 to 'x' to get $(n^2 + \frac{n}{2} + 1)^2$ . The case for n odd is similar.

That seemed really clear in my head but might be a bit of a mess here... Hope you can follow it!

Thread: Proof by Induction?

LinkBack

Thread Tools

Display

Mathematical Inspiration

All In A Nutshell

Similar Math Help Forum Discussions

Proof by Induction

Proof by Induction

Mathemtical Induction Proof (Stuck on induction)

Proof by Induction??

Proof with algebra, and proof by induction (problems)

Search Tags