oak pier
Hi everyone! I'm looking to solve this problem, but I do not really have any idea where to start with it. Particularly, I am not well-versed in proving, though I am not sure if that
's all there is to it. Any resources that I can take a look at to help? Thanks!
keen stagBOT
cobalt wave
Do you know how to find the thing in the last row (the direct formula for Fibonacci numbers)
oak pier
Yes! The next number is the sum of the preceeding two
cobalt wave
That is called the recurrence formula. Do you know how to get the direct formula?
Recurrence formule is for example a_n=2a_(n-1)+a_(n-2) with a_1=3 and a_2=6. A direct formula is for example a_n=3*2^n-5^n or something like that. With the recurrence formula you have to know all the previous terms to calculate the next one but with the dorect formula you can easily calculate high terms like a_2023
cobalt wave
Do you just want to use the hint that Fib(n)=(phi^n-psi^n)/sqrt5 or do you also want to prove it?
oak pier
I want to understand how I can answer the question 😃
cobalt wave
Does this help you?
oak pier
Here's what I came up with
lethal granite
The hint tells you to use induction, which is a very specific type of proof. If you don't know it, I suggest looking up YouTube videos on the topic of proof by induction.
oak pier
Here's what I came up with
Isn't this a build-up to that? Is this wrong?
lethal granite
Here's what I came up with
This is a good start on the algebra.
Don't be afraid to use English words to say what you're doing. In fact, your proof needs to have words in it. That's the point.
To continue the algebra, you'll need to use the actual values of phi and psi.
It also helps to make notes on scrap paper of the end point that you're actually aiming for in the algebraic computation.
gleaming ocean
Do you recognize what φ and ψ are?
oak pier
Do you recognize what φ and ψ are?
Yes, they are noted in the question
Thanks for the advice @lethal granite will do!
gleaming ocean
Yes, they are noted in the question
I mean from other contexts, because they show up elsewhere
a bit
φ is called the "golden ratio"
oak pier
Ohh, really now? Never knew. Where else does it come up?
gleaming ocean
most of them are bit of a spoiler to this question actually
one neat property is that it can be written as
1 + 1/(1 + 1/(1 + 1/...))
every number can be written in the form
a + 1/(b + 1/(c + 1/...))
where a, b, c, ... are integers. This "continued fraction" will go on forever if the number is irrational, but cutting it off after a few terms gives you a rational approximation of whatever number it is
Here's pi, for example: https://blogs.scientificamerican.com/blogs/assets/File/continued fraction pi.jpg
3+1/7 = 22/7 is a pretty famous approximation
now, the larger the numbers a, b, c... are, the more "significant" they are to the accuracy of the approximation
so the approximation for pi [3; 7, 15, 1] may not be that much better than [3; 7, 15], but [3; 7, 15, 1, 292] should be a relatively large improvement (and indeed, 355/113 is an excellentapproximation)
([a; b, c, ...] is the notation for these things)
my point in all of this is that φ = [1; 1, 1, 1, ...] has the smallest a, b, c, ... possible
so it has very bad rational approximations
the worst rational approximations, in some sense
so you sometimes hear it called the "most irrational" number
oak pier
To continue the algebra, you'll need to use the actual values of phi and psi.
I'm working through this now. Though it seems a complicated and not complicated at the same time
lethal granite
Yeah, it's a bit of an equation to work with. It might help to know stuff like phi^2 = phi + 1, but not knowing that just means you have to play around with it a bit more.
oak pier
Here's what I came up with
So, for the (phi^k - psi^k), I endud up with (2(5^(k/2)) + 2)/2^(k). How far off is this 😅
lethal granite
Here's what I came up with
This is good. You should gather like terms by factoring out phi^(k-1) and psi^(k-1).
lethal granite
So, for the `(phi^k - psi^k)`, I endud up with `(2(5^(k/2)) + 2)/2^(k)`. How far...
What you would do from here is: start again with the final answer that you want and simplify it back to this; then put the two halves together.
oak pier
Question! Does x**k-1 equal (x**k)/x?
oak pier
So, I think I solved this using the notion that Φ^2 = Φ + 1 or Φ^2 = Φ^1 + Φ^0. Therefore, Φ^k = Φ^k-1 + Φ^k-2
The same applies to ψ as ψ^2 = ψ + 1
Will write up a formal proof and post here for feedback
oak pier
Essentially, I simplified the presence of Φ^k + Φ^k - 1 to Φ^k+1 based on the above exponential relationship. Is this too much of a leap in logic?
lethal granite
No, that's not too much of a leap, though you can assure it more directly if you include one extra line where you common factor out phi^(k-1)
oak pier
No, that's not too much of a leap, though you can assure it more directly if you...
What do you mean?
oak pier
So here's my draft proof. Let me know what y'all think
Also, does the proof answer the original question at the top of this post?
lethal granite
It's almost there, but there are two little corrections to be done.
In the first page, you have a ... in your calculation where you did a few examples and then generalized to k.
That's not the worst, but it's completely unnecessary. Start with phi^k + phi^(k-1), and common factor out as much as you can.
Then it's a single more explicit calculation.
In the second page, you are trying to prove the formula for Fib(n+1), but you used the formula in the second line!
When you're doing proof calculations like that, you should only be working down the right hand side, and it should end with the formula that you want.
oak pier
That's not the worst, but it's completely unnecessary. Start with phi^k + phi^(k...
So just the generalizarion, no need for the examples?
oak pier
When you're doing proof calculations like that, you should only be working down ...
Oh! So the formula ought to appear at the end correct?
lethal granite
As for the original question, once you have the formula, you just need to show that psi ^k is small
lethal granite
So just the generalizarion, no need for the examples?
Yes, but you should prove the generalisation.
oak pier
Yes, but you should prove the generalisation.
How do I do that?
oak pier
Yes, but you should prove the generalisation.
Like this?
lethal granite
Not quite. Two issues with the this. First of that you haven't done it for general exponents, just two examples. Second is that you're writing down an equation that you want to prove and then simplifying it to something you know is true. But you started by declaring as true the thing that you want to prove is true.
You should start with phi^k + phi^(k-1), then do simplifications to that until you get to phi^(k+1).
oak pier
Hi, just wanted to say I'm still on this. Will hopefully have it down this week. Thank you guys for the help thus far. This is the closest I have ever been!
pliant sonnet
There is a simple way to prove it actually
There are three things to prove:
But first let’s define what Gibonacci means
A sequence a(n) is Gibonacci if a(n)+a(n+1)=a(n+2)
This is like the Fibonacci sequence except the first two numbers may be different and then it goes from there…
So the three things to prove:
Each of these should be easy to prove
Good luck 👍
I will give an example of the first one
And there is the third
It may come as a surprise that psi^n is Gibonacci
But yeah
I believe there are only three numbers c for which c^n is Gibonacci
And they are 0,phi, and psi
I could try to prove that fact but keep in mind it isn’t really necessary for this problem
So psi = -1/phi
Using linear combinations of phi^n and psi^n you can get Gibonacci sequences with whatever numbers you want for the first two numbers in the sequence
However, the first two numbers in a Gibonacci sequence determine all the numbers in the sequence that follow
Thus all Gibonacci sequences are a linear combination of phi^n and psi^n
They already give you what c and d you need to get the Fibonacci sequence
Namely c = 1/sqrt(5) and d = -1/sqrt(5)
I’ll leave the proof that psi^n is Gibonacci as an exercise because it is similar to the proof that phi^n is Gibonacci
Well I kind of proved it in the last picture though…
lethal granite
That is definitely not easier. It both requires advanced knowledge/creativity to start, and it actually takes longer. The proof that Ola is going for is like 5 lines once you understand the structure of induction and see how to add x^k + x^(k-1) by factoring out an x^(k-1), which is a necessary step for showing phi and psi are Gibonacci anyway.
pliant sonnet
I could try to prove that fact but keep in mind it isn’t really necessary for th...
^
pliant sonnet
There are three things to prove:
^
lethal granite
Yes, I read what you wrote. I'm aware that you don't need to prove that those are the only geometric Gibonacci sequences. But that's still way more work than just answering the question.
pliant sonnet
oak pier
You should start with phi^k + phi^(k-1), then do simplifications to that until y...
So, doing some thinking, and consulting back and forth with ChatGPT, here is what I came up with, though, I'm not sure if it's correct. But if it is, why?
lethal granite
That's right, though it's a bit of an odd way of doing it
p^k + p^(k-1) = p^(k-1) (p + 1)
=p^(k-1) (p^2)
=p^(k+1) flows much better
oak pier
That's right, though it's a bit of an odd way of doing it
Glad it's right, though I am not sure why we're using phi^2 = phi + 1. Why is that included?
lethal granite
You can just plug in for phi to calculate that
oak pier
p^k + p^(k-1) = p^(k-1) (p + 1)
=p^(k-1) (p^2)
=p^(k+1) flows much better
Before the factorization at p^k + p^(k-1) = p^(k-1) (p + 1), did you have p^k + p^(k-1) = p^(k-1) + p^k?
lethal granite
All of the math is there but there are a few issues of formatting and one sign error.
If this is an assignment, you're probably getting most of not all of the marks.
If you like math or you're planning to study more of it, it's probably worth looking at the nuances of the argument, because it will help your understanding and proof writing.
I appreciate that it's a bit slow and complicated to work through.
When I'm next at my computer, I'll show you the details.
lethal granite
Here you start and end in the same place. That's bad.
Just this (without the first equals sign) is much better
Check this again
Same issue here as above. Don't start and end in the same place.
F(n+1) uses F(n) and F(n-1), so your base case needs to be two equations.
Finally, here you plugged in on the left hand side for Fib(n+1), but you plugged in the equation that you're trying to prove!
And then dividing both sides by root 5 is bad too.
You're not working with an equation and solving it.
You're starting with an expression and simplifying it until it becomes the thing you want it to be.
Every single expression in your argument here should be equal.
Keep the root 5, don't put anything else on the left side.
Btw, if I didn't mention it before, I'm impressed by your patience to want to get this right. 😄
oak pier
Here you start and end in the same place. That's bad.
Interesting you say that. I thought doing it this way would make the relation much more explicit. Might I ask why this is wrong in the world of maths?
oak pier
Check this again
Is the equation wrong?
oak pier
F(n+1) uses F(n) and F(n-1), so your base case needs to be two equations.
So both F(n) and F(n - 1)?
oak pier
Btw, if I didn't mention it before, I'm impressed by your patience to want to ge...
Thank you for the kind words. I am trying my best, but it seems like I might need to learn how to write proofs just so I can better understand the reasoning behind your comments and not make these silly mistakes, but most importantly, understand why these are mistakes. Any resources?
lethal granite
Interesting you say that. I thought doing it this way would make the relation mu...
The argument wants to be that one thing equal another thing, not that one thing equals itself. You also need to be careful about what assumptions you're making. For example, in the last section you assume the very thing that you're trying to prove.
lethal granite
Is the equation wrong?
Yes, your equation with psi is wrong.
lethal granite
So both `F(n)` and `F(n - 1)`?
The base case needs to have both F(0) and F(1).
There's a book by Velleman called How to Prove It.
Mostly it's just practice reading and writing proofs and paying attention and asking good questions.
Another tip which I'll just quote:
People tend to think "math is about symbols", but it's not. It's about communicating, and the vast majority of people learning to write proofs would benefit from writing more English text.
oak pier
Great! I got the book: "https://www.amazon.com/How-Prove-Structured-Daniel-Velleman/dp/1108439535"
But....errr, will I need to go through the entire book or just up to chapter 3
ripe pier
I also got: https://www.amazon.com/Proofs-Long-Form-Mathematics-Textbook-Math/dp...
I was about to recommend this lol I have the same exact book
page 200 If I recall discusses fibonachi sequences
nvrmd that discusses how to define the golden ratio via fibonachi sequences
ripe pier
People tend to think "math is about symbols", but it's not. It's about communica...
very good point, also I'll put that book on my amazon list to get. Since the only book on proofs that I have is the one seen above, and a brief section in a IMO practice book
lethal granite
I haven't read the book. I didn't really even do a course on proofs. But I learned induction early on and got comfortable with it, then did a university course full of proofs. It was a bit of trial by fire.
oak pier
Yeah the second book caught my eye. I figured it'd be a good read. Though I am unsure if it assumes any pre-existing knowledge from the reader
Are there pre-reqs to writing proofs btw?
lethal granite
Basically no. You just need to know whatever is s specific to that topic.
Usually people start with trigonometry, simple algebra, and elementary number theory because they require the least amount of knowledge.
Also geometry stuff, like similar triangles and parallel lines.
oak pier
Oh, then I can get right into it then? Or what would you suggest?
lethal granite
Just start reading the books when you get them and ask here if you don't understand something
You can look on khan academy for triangle proofs or trigonometric identity proofs. They're not quite of the same quality as the proofs that you want to learn, but they're a good start if you haven't done them.
oak pier
Alright! Thank you for the suggestions. I really appreciate it. Though, the book you advised, it seems like only Chapter 3 is centered on proofs. Would you recommend also reading the subsequent chapters too?
lethal granite
The entire book is about proofs. Chapters 1 and 2 are pre-requisites, chapter 3 starts on proofs, and then the rest of the book is about proofs in different contexts.
oak pier
So, @lethal granite I just got done with the exercises in the intro chapter. Was hoping you could help me look over my answers
Particularly, my answer to question 6
oak pier
lethal granite
I'm not sure what theorem 4 is, but I don't think it's right. It's true that the average gaps between primes increases, but there continues to be infinitely many occurrences of pairs of primes that are very close together.
The proof for question 6 is very short and precise and algebraic. You should try to search for another triple like 3,5,7 and see what goes wrong
oak pier
Theorem 4 is: For every positive integer n, there is a sequence of n consecutive positive integers containing no primes.
The proof for question 6 is very short and precise and algebraic. You should try to search for another triple like 3,5,7 and see what goes wrong
How do you suppose I go about this?
In the context of deductive reasoning, it is true that a conclusion is considered true so long as all it's premises are also considered true?
lethal granite
> The proof for question 6 is very short and precise and algebraic. You should t...
Wait, are you asking about sequences of n consecutive positive integers containing no primes, or are you asking about the lack of triplets?
If you need to prove theorem 4, you can use the same strategy that you used to find 5 consecutive non-primes. But maybe you know that because you already have a proof of theorem 4.
The advice for question 6 is just to try to find another triple like 3,5,7. Even though you know you won't be able to find such a triple, the search is worthwhile.
You know 11 and 13 is already most of the way there, so you try 9,11,13 and 11,13,15.
You know 17,19 is close, so you try 15,17,19, and 17,19,21.
You know 29,31 is close, so you try 27,29,31 and 29,31,33
None of the those new numbers we tried are prime.
But maybe the way that they failed to be prime can give you a hint.
