Is there a way to guarantee that the sequence will eventually reach 0?

  • MHB
  • Thread starter Ackbach
  • Start date
  • Tags
    2017
In summary, there are mathematical techniques, such as bounding and using mathematical induction, that can be used to prove that a sequence will eventually reach 0. However, there is no formula or algorithm that guarantees this for all sequences, as it depends on individual properties. While computer simulations can aid in understanding a sequence, mathematical proofs are necessary for guaranteeing convergence. In some cases, convergence to 0 can be optimized through patterns or mathematical manipulation, but in others, it is determined by the nature of the sequence. Understanding sequences that eventually reach 0 has real-life applications in fields such as computer science, engineering, finance, and physics.
  • #1
Ackbach
Gold Member
MHB
4,155
92
Here is this week's POTW:

-----

Let $f(x)$ be a polynomial with integer coefficients. Define a sequence $a_0,a_1,\ldots$ of integers such that $a_0=0$ and $a_{n+1}=f(a_n)$ for all $n\geq 0$. Prove that if there exists a positive integer $m$ for which $a_m=0$ then either $a_1=0$ or $a_2=0$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!
 
Physics news on Phys.org
  • #2
Re: Problem Of The Week # 264 - May 23, 2017

This was Problem A-6 in the 2000 William Lowell Putnam Mathematical Competition.

Congratulations to Kiwi for his correct solution, which follows:

Let \(f(x)=\sum^r_0 b_ix^i.\)

Then
\(a_0=0\), \(a_1=f(a_0)=f(0)=b_0\), \(a_2=f(b_0)\)

Now if \(a_m=0\) then \(f(a_{m-1})=0\) and \(a_{m-1}\) is a root of f(x). Therefore

\((x-a_{m-1})\) divides \(\sum^r_0 b_ix^i,\) from which we can see that \(a_{m-1}\) divides \(b_0\) as they are all integers.

Case 1; \(b_0 = 0\)
\(a_1=f(a_0)=f(0)=b_0=0\) and we are done.

Case 2; \(b_0 \neq 0\)
Now \(b_0\) divides \(a_1\) because they are equal. Assume as an inductive hypothesis that \(b_0\) divides all \(a_i\) then
\(a_{n+1}=f(a_n)= \sum^r_1 b_i(a_n)^i+b_0\) which is divisible by \(b_0\). So by induction \(b_0\) divides all \(a_i\).

So \(b_0\) divides \(a_{m-1}\) and \(a_{m-1}\) divides \(b_0;\) therefore \(a_{m-1}=b_0\) and therefore

\(a_2=f(a_1)=f(b_0)=f(a_{m-1})=a_m=0.\)
 

FAQ: Is there a way to guarantee that the sequence will eventually reach 0?

How can we guarantee that a sequence will eventually reach 0?

There are a few mathematical techniques that can be used to prove that a sequence will eventually reach 0. One method is to show that the sequence is bounded below by 0 and that it decreases with each iteration. Another method is to use the principle of mathematical induction to show that the sequence will eventually reach 0.

Is there a specific formula or algorithm to ensure that a sequence will reach 0?

There is no one-size-fits-all formula or algorithm to guarantee that a sequence will reach 0. The approach will depend on the specific sequence and its properties. However, there are general techniques and principles that can be applied to prove convergence to 0.

Can we use computer simulations to verify that a sequence will eventually reach 0?

Computer simulations can be a useful tool to support our understanding and analysis of a sequence. However, they cannot be used as a substitute for mathematical proofs. In order to guarantee that a sequence will eventually reach 0, we must use mathematical techniques and principles.

Is there a way to speed up the convergence to 0 in a sequence?

In some cases, there may be ways to optimize or improve the convergence of a sequence to 0. This could involve finding patterns or using mathematical properties to manipulate the sequence. However, in other cases, the convergence may be determined by the nature of the sequence itself and cannot be altered.

Are there any real-life applications for understanding sequences that eventually reach 0?

Absolutely! Understanding sequences that eventually reach 0 is crucial in many fields such as computer science, engineering, finance, and physics. In computer science, for example, this concept is used in algorithms for searching and sorting data. In finance, it can help with analyzing stock market trends. And in physics, it can help predict the behavior of systems over time.

Similar threads

Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
1K
Replies
1
Views
1K
Back
Top