/sci/ - Science & Math

Trivial induction. Next!

>>4307174

>>4307220
reported for redditor

>>4307270
this

>implying /sci/ is browsed by Olympiad level math geeks
>implying the problem proposed has any practical applications
>implying anybody gives a shit about it

>>4307360
>implying you aren't new here or a troll

>>4307360
>implying /sci/ is browsed by Olympiad level math geeks
Well, it's not Olympiad level to be able to solve Olympiad problems given time and collaboration, you know. I'm clearly not Olympiad level, but I'm able to contribute (and sometimes solve on my own) a decent fraction of the problems that are posted here.

Just solve for a.
<span class="math">x_{n+1} = ax_n - x_n[/eqn]
<div class="math">a = \frac{x_{n+1} + x_{n}}{x_n}</div>

I guess we have to show that this number is the same for each n.[/spoiler]

>>4307360
All three implications are true. How does that feeling for you?

Just solve for a.
<span class="math">x_{n+1} = ax_n - x_n[/spoiler]
<div class="math">a = \frac{x_{n+1} + x_{n}}{x_n}</div>
I guess we have to show that this number is the same for each n.

>>4307385
Well, I'm not so sure about the second implication. But I don't see why that would matter.

The sequence described in the problem is the set of positive integers in order from smallest to greatest. Not sure if this is the only set of reals that has these characteristics

im playing around with ideas so find answer

already found the answer, latexing that shit for you guys.

>>4307393
fuck, I I dropped the minus 1.
<span class="math">x_{n+1} = ax_n - x_{n-1}[/spoiler]
<div class="math">a = \frac{x_{n+1} + x_{n}}{x_n-1}</div>
3rd times the charm?

FUCK, 4th time?
<span class="math">x_{n+1} = ax_n - x_{n-1}[/spoiler]
<div class="math">a = \frac{x_{n+1} + x_{n-1}}{x_n}</div>

>>4307476
Alright, just working backwards.
We want to show that
<div class="math">\frac{x_{n+1}+x_{n-1}}{x_n} = \frac{x_{n+2}+x_{n}}{x_{n+1}}</div>
Multiplying both sides by <span class="math"> x_nx_{n+1}[/spoiler] gives us
<div class="math">x_{n+1}^2 +x_{n+1}x_{n-1} = x_n^2 + x_{n+2}x_n</div>
Subtracting the nonsquares shows that each side is equal to 1.
<div class="math">x_{n+1}^2 - x_{n+1}x_n = x_n^2 - x_{n+1}x_{n-1} </div>
I guess it's not good that I started with assuming something to prove, so just do the steps in reverse.

>>4307418
from this we take that Xn = n
(Xn)^2 -(Xn-1)(Xn+1) = 1
n^2 - (n-1)(n+1) = 1
n^2 - (n^2-1) = 1
1 = 1
true

so
Xn+1 = aXn - Xn-1
n+1 = an -(n-1)
n+1 = an -n+1
2n = an

a = 2

>>4307565
>I guess it's not good that I started with assuming something to prove, so just do the steps in reverse.
It's okay if you find the actual value of a.

You'll just have to test the value you found and if it works, you found the answer.

>>4307476
Good stuff.

We want to find <span class="math">a[/spoiler] such as


<span class="math">x_{n+1}-ax_n + x_{n-1}=0[/spoiler]
(linear 2nd order recurrence) <span class="math">r^2-ar+1=0[/spoiler]

<span class="math">\Delta= a^2-4 [/spoiler] I'll look for a such as <span class="math"> a > 2 [/spoiler] let <span class="math"> a'=\frac{a}{2}[/spoiler]
the roots are
<span class="math">r_1= a'- sqrt(a'^2-1)[/spoiler] and
<span class="math">r_2= a'+sqrt(a'^2-1)[/spoiler]

<span class="math">\forall n \in \mathbb{N}[/spoiler], there exists <span class="math">k,l \in \mathbb{R}[/spoiler] such as
<span class="math">x_n= k*r_{1}^n + l* r_{2}^n[/spoiler]
then:
<span class="math">x_{n}^2-x_{n-1}*x_{n+1} = (k* r_{1}^n + l* r_{2}^n)^2 - (k* r_{1}^{n-1} + l* r_{2}^{n-1})(k* r_{1}^{n+1} + l* r_{2}^{n+1})[/spoiler]
which can also be written:

<span class="math">k^{2}* r_1^{2n} + l^{2}r_{2}^{2n} + 2kl(r1r2)^n - k^{2} r_{1}^{2n} -l^{2} r_{2}^{2n} - kl( r_{1}^{n-1}r_{2}^{n+1} +r_{1}^{n+1}r_{2}^{n-1})

=kl*(2 -( r_{1}^{n-1}r_{2}^{n+1} + r_{1}^{n+1}r_{2}^{n-1}) [/spoiler] because <span class="math">r_{1}r_{2}=1 [/spoiler]


so I have <span class="math">kl*(2 -( r_{1}^{n-1}r_{2}^{n+1} + r_{1}^{n+1}r_{2}^{n-1}) = 1[/spoiler]

which is also
<span class="math">kl* (2 - (r_{1}+r_{2}))=1[/spoiler]

but <span class="math">r_{1}+r_{2}=a[/spoiler]

therefore I have to obtain <span class="math">kl*(2-a)=1[/spoiler]
as <span class="math">a>2[/spoiler], it can be true. And as <span class="math">kl(2-a)=1[/spoiler], <span class="math"> kl != 0 [/spoiler]
Therefore I need <span class="math">a= 2- \frac{1}{kl}[/spoiler]

<span class="math">k[/spoiler] and<span class="math"> l [/spoiler] are defined by <span class="math">x_0[/spoiler] and <span class="math">x1[/spoiler].
So by setting <span class="math">a= 2-\frac{1}{kl}[/spoiler], I can write <span class="math"> \forall n \in \mathbb{N}, x_{n+1}=ax{n}-x{n-1} [/spoiler]

>>4307565
Sounds ok.

>>4307667
I just have to check that <span class="math"> kl [/spoiler] is indeed negative,

Did anyone solve yesterday's problem?

>>4307697
what was yesterday's problem?

>>4307721
here's the link that was on yesterday's problem:
http://www.math.harvard.edu/putnam/

4307734

>>4307734

>>4307734
yeah, has anyone saved the pic?

>>4307759
it's right here
>>4299956
hasn't even 404'd...

ehh...
(x_n)^2 = 1 + (x_n-1)(x_n+1) suggests that neither (x_n-1) nor (x_n+1) can be a factor of x_n, so the sequence must be alternating odd and even, which is possible if (x_n+1) = 2(x_n) - (x_n-1).

... so a=2?
Either that's trivial or I went full retard. Probably the latter.

>>4308057
Erhm, nobody said it was integers.

i don't know how to do the actual proof

a=2 only for certain series

1,2,3,4,5,6,7... fits the specifications and a=2 but

3, 10, 33, 108.8, 358.68 also fits and a=3.6. also note they are no longer integers

1, 0, -1, 0, 1, 0, -1 also fits with a=0. again now the series isn't constantly increasing

>>4308499
The x_n are positive.

>>4307565
>>4307476
The proof is here and easy enough to follow.

Much easier than yesterday's problem. Note that
<div class="math">
x_{n+1} = \left(\frac{x_n^2 +x_{n-1}^2 -1}{x_n x_{n-1}}\right) x_n - x_{n-1}.
</div>
Easily, we can show that that <span class="math">a_n := \frac{x_n^2 +x_{n-1}^2 -1}{x_n x_{n-1}}[/spoiler] is constant in <span class="math">n[/spoiler]:
<div class="math">
a_{n+1} = a_n
</div>
iff
<div class="math">
\frac{x_{n+1}^2 +x_n^2 -1}{x_{n+1}} = \frac{x_n^2 +x_{n-1}^2 -1}{x_{n-1}}.
</div>
Substitute <span class="math">x_n^2 = 1+x_{n-1}x_{n+1}[/spoiler] in the numerators of both sides of the equation and simplify to see that we indeed do have an equality.

Therefore, the desired result is true with
<div class="math">
a = \frac{x_0^2 +x_1^2 -1}{x_0x_1}.
</div>

First time on /sci/ ... I usually go on /b/ and /fit/, with a tad of /lit/. You guys are such nneerrrddddssss

>>4309327
reported

>>4309327
NERRRRDS

If such a series exists, then x^2 - (x-f)(x+g) = 1 for some real f, g for each x in the series, except for the first one.

f = (x_n) - (x_n-1)
g = (x_n+1) - (x_n)

so, x^2 - (x-f)(x+g) = 1
rearrange it to get fx + fg -gx = 1
solve for x to get
x = (g-f)[(fg-1)/(f-g)^2] <- EQ K manystepsomitted

We have to show that a exists when x+g = ax-(x-f)
rearrange this to obtain x = (g-f)[1/(a-2)]
compare to EQ K, notice that
1/(a-2) = (fg-1)/(f-g)^2

then a = [(f^2 - 2fg+g^2)/(ab-1)] + 2

Undefined where f = g, as in the case of all positive integers. but if f = g = 1 it is easy to show that a is 2

Here's what I got. You've got to use induction, which takes two steps.
Step 1: Prove there is a value of a that works for a single case
(n = 1).
Rewrite identity as:
<div class="math"> x_2 = \frac{x_1^2-1}{x_0} = a x_1-x_0 </div>
Solve for a to get <span class="math"> a = \frac{x_0^2+x_1^2-1}{x_0 x_1} [/spoiler].
So a exists for all nonzero <span class="math"> x_0 [/spoiler] and <span class="math"> x_1 [/spoiler].

Step two, assuming that the condition is true for an arbitrary case, n, prove that it is also true for n+1:
In other words, assume <span class="math"> x_{n+1} = a x_n - x_{n-1} [/spoiler] and use it to show that <span class="math"> x_(n+2) = a x_{n+1} - x_n [/spoiler].

Rewrite the assumption as <span class="math"> x_{n-1} = a x_n - x_{n+1} [/spoiler] and substitute it into the identity, <span class="math"> x_n^2 - x_{n-1} x_{n+1}=1[/spoiler], to get rid of <span class="math"> x_{n-1} [/spoiler].
This gives you: <div class="math"> x_n^2-a \left(a x_n - x_{n+1} \right) x_{n+1} = 1 </div>
Which can be rewritten as:
<div class="math"> \frac{x_{n+1}^2-1}{x_n}=a x_{n+1}-x_n [\eqn].
By solving the identity, <span class="math"> x_{n+1}^2-x_n x_{n+2}=1 [/spoiler] for <span class="math"> x_{n+2} [/spoiler], you can see that <span class="math"> x_{n+2} [/spoiler] is equal to the left hand side. This what we were going for, so we proved the relation with induction. Yay! We shall commence celebration with champagne, weed, and hookers.</div>

Here's what I got. You've got to use induction, which takes two steps.
Step 1: Prove there is a value of a that works for a single case
(n = 1).
Rewrite identity as:
<div class="math"> x_2 = \frac{x_1^2-1}{x_0} = a x_1-x_0 </div>
Solve for a to get <span class="math"> a = \frac{x_0^2+x_1^2-1}{x_0 x_1} [/spoiler].
So a exists for all nonzero <span class="math"> x_0 [/spoiler] and <span class="math"> x_1 [/spoiler].

Step two: Assuming that the condition is true for an arbitrary case, n, prove that it is also true for n+1:
In other words, assume <span class="math"> x_{n+1} = a x_n - x_{n-1} [/spoiler] and use it to show that <span class="math"> x_{n+2} = a x_{n+1} - x_n [/spoiler].

Rewrite the assumption as <span class="math"> x_{n-1} = a x_n - x_{n+1} [/spoiler] and substitute it into the identity, <span class="math"> x_n^2 - x_{n-1} x_{n+1}=1[/spoiler], to get rid of <span class="math"> x_{n-1} [/spoiler].
This gives you: <div class="math"> x_n^2-a \left(a x_n - x_{n+1} \right) x_{n+1} = 1 </div>
Which can be rewritten as:
<div class="math"> \frac{x_{n+1}^2 - 1}{x_n} = a x_{n+1} - x_n </div>.
By solving the identity, <span class="math"> x_{n+1}^2-x_n x_{n+2}=1 [/spoiler] for <span class="math"> x_{n+2} [/spoiler], you can see that <span class="math"> x_{n+2} [/spoiler] is equal to the left hand side. This what we were going for, so we proved the relation with induction. Yay! We shall commence celebration with champagne, weed, and hookers.
P.S. Sorry about the 'unknown control sequence' earlier.

Well done. This is definitely one of the easier problems on the Putnam

Hitler was trying too Hard

>>4311096
What?

>>4310050
Agreed. Although it took me longer than it should have because I got mired in an approach similar to >>4307667

I guess I assumed the solution couldn't possibly be as easy as a straightforward induction, so I didn't even bother to first check if such an approach would work.