Fekete's Lemma: Proof & Understanding

  • Thread starter CoachZ
  • Start date
In summary, Fekete's Lemma is a mathematical theorem used to prove the existence of an optimal solution in certain optimization problems. It is typically proven using the method of contradiction and has applications in various fields. The main idea behind the lemma is that a bounded sequence with a limit equal to its supremum (or infimum) must converge to that supremum (or infimum). However, Fekete's Lemma has limitations in that it can only be applied to certain problems and does not provide a method for finding the optimal solution.
  • #1
CoachZ
26
0
Fekete's Lemma states that if {a_n} is a real sequence and a_(m + n) <= a_m + a_n, then one of the following two situations occurs:
a.) {(a_n) / n} converges to its infimum as n approaches infinity
b.) {(a_n) / n} diverges to - infinity.

I'm trying to figure out a way to show either of these things happen but can't seem to do it. Does anyone have the proof of this or have suggestions to go about proving it.
 
Physics news on Phys.org
  • #2
a) Suppose the {a_n/n} converges to some number A. Show that A is the inf.
 

FAQ: Fekete's Lemma: Proof & Understanding

What is Fekete's Lemma?

Fekete's Lemma is a mathematical theorem that is used to prove the existence of an optimal solution for a certain optimization problem. It is often used in areas such as economics, operations research, and computer science.

How is Fekete's Lemma proven?

Fekete's Lemma is typically proven using the method of contradiction. This involves assuming that there is no optimal solution and then showing that this leads to a contradiction. By doing so, it can be concluded that an optimal solution must exist.

What is the significance of Fekete's Lemma?

Fekete's Lemma is significant because it provides a powerful tool for proving the existence of an optimal solution in certain optimization problems. It has applications in various fields, including game theory, economics, and computer science.

Can you explain the main idea behind Fekete's Lemma?

The main idea behind Fekete's Lemma is that if a sequence of real numbers is bounded above (or below) and its limit superior (or inferior) is equal to its supremum (or infimum), then the sequence must converge to that supremum (or infimum).

Are there any limitations to Fekete's Lemma?

Yes, Fekete's Lemma has certain limitations. It can only be applied to certain types of optimization problems, and it does not provide a method for finding the actual optimal solution. It only proves the existence of one.

Similar threads

B Showing that a sequence of supremums of a sequence has these two properties
Replies
4
Views
2K
I How does the ratio test fail and the root test succeed here?
Replies
6
Views
2K
B Continuation of sequence of supremums question
Replies
9
Views
1K
I What is the difference between these two power series theorems?
Replies
5
Views
918
I Question about uniform convergence in a proof
Replies
1
Views
1K
I Question regarding a sequence proof from a book
Replies
3
Views
1K
I Spivak, Ch. 20: Understanding a step in the proof of lemma
Replies
1
Views
2K
Simple Induction Help with Lemma for proof of AM-GM inequality
Replies
6
Views
2K
On the ratio test for power series
Replies
2
Views
1K
MHB Proof of $\lim_{{n}\to{\infty}}a_n=\lim_{{n}\to{\infty}}b_n$ with $\epsilon-N$
Replies
7
Views
2K

Hot Threads

Recent Insights

Back
Top