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.
 

1. 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.

2. 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.

3. 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.

4. 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).

5. 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

Replies
6
Views
477
Replies
9
Views
834
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
640
  • Math Proof Training and Practice
Replies
6
Views
1K
Replies
3
Views
1K
Replies
11
Views
806
Replies
15
Views
2K
Replies
13
Views
1K
Back
Top