1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Convergence of a recurrence equation: x(k+1) = 0.5x(k) + u(k)

  1. Mar 25, 2012 #1
    1. The problem statement, all variables and given/known data

    Hello. I am trying to prove a result that I have been making use of, but never really proved. Consider the recurrence equation

    [itex]x(k+1) = 0.5 x(k) + u(k)[/itex],

    where u(k) is a bounded sequence. For this problem, assume that u(k) goes to zero. I want to prove that x(k) goes to zero.

    2. Relevant equations

    If I use recursive substitution, I get for any k

    [itex]x(k) = 0.5^{k}x(0) + \sum_{i=0}^{k-1}0.5^{i}u(k-i)[/itex]

    3. The attempt at a solution

    The first thing that came to my mind was to sandwich x(k) between two sequences that both went to zero. But I'm having some trouble bounding this relation. So the first thing I like to do to get an idea of how to proceed is to consider a simple input u(k) = 1/k. In this case, the recursive relation becomes

    [itex]x(k) = 0.5^{k}x(0) + \sum_{i=0}^{k-1}\frac{0.5^{i}}{k-i}[/itex]

    The first term is easy to bound. But what can I do with the second term. Can I make use of u_min = min(u(k)) and u_max = max(u(k)) in some special way?

    Can someone suggest some techniques or theorems that I can use to prove that x(k) goes to zero?
  2. jcsd
  3. Mar 25, 2012 #2
    Have you tried replacing u(k-i) by M, where M = max(u(k))? M exist because in the problem statement u(k) is bounded.

    Then use the sum of a geometric series formula.
  4. Mar 26, 2012 #3
    Hi. Thanks a lot for replying.

    If I replace 0.5^{i}u(k-i) by M where M is it's max value, then I can get an upper bound on x(k). But this upper bound might blow up as k tends to infinity (for the case where M>1). I won't be able to conclude what happens to x(k) as k tends to infinity.
  5. Mar 26, 2012 #4

    Replace u(k-i) with M. You get 0.5^{i}M. The sum of 0.5^{i} is known using the geometric series formula.

    Anyway, forget that for now.

    What you actually need is to use is the fact that if u(k) -> 0 the there exist a [itex] k_{0}[/itex] such that [itex] |u(k)| < \epsilon [/itex] for all [itex] k > k_{0}[/itex].

    It is easy to show that [itex] 0.5^{k}[/itex] also tends to zero. So you could probably use the triangle inequality to get an epsilon to show that [itex] |x(k)| < \epsilon_{1,2}[/itex].
    Last edited: Mar 26, 2012
  6. Mar 26, 2012 #5
    Sorry about that. I understand and can solve it now. Thanks.
  7. Mar 26, 2012 #6
    Can you post your solution attempt ?
  8. Mar 26, 2012 #7
    -- Show that x(k) goes to zero in the limit.

    Let [itex] \epsilon > 0 [/itex]. Now, we know that [itex] 0.5^{k} [/itex] and [itex] u(k) [/itex] both go to zero, therefore, for all [itex] \epsilon_{1} > 0 [/itex], there exists [itex] k_{1}>0[/itex], such that if [itex] k > k_{1}[/itex], then [itex] | 0.5^{k} | < \epsilon_{1}[/itex] and [itex] | u(k) | < \epsilon_{1}[/itex]. Now

    [itex] x(k) = | 0.5^{k} x(0) + \sum_{i=0}^{k-1} 0.5^{i} u(k-i) |[/itex]

    [itex]< | \epsilon_{1} x(0) + \sum_{i=0}^{k-1} 0.5^{i} \epsilon_{1} | [/itex] for all [itex] k > k_{1}[/itex]

    [itex]= | \epsilon_{1} x(0) + \frac{\epsilon_{1}(1-0.5^k)}{0.5} | [/itex]

    [itex]= | \frac{0.5\epsilon_{1} x(0) + \epsilon_{1}(1-0.5^k)}{0.5} | [/itex]

    [itex]= \epsilon_{1}| \frac{0.5 x(0) + (1-0.5^k)}{0.5} | [/itex]

    Choose [itex]k_{1}[/itex] such that

    [itex] \epsilon_{1}| \frac{0.5 x(0) + (1-0.5^k)}{0.5} | < \epsilon[/itex]

    Now, for all [itex] \epsilon > 0[/itex], there exists [itex] k_{1}[/itex] such that [itex] k > k_{1}[/itex] implies
    [itex]|x(k)| < \epsilon[/itex]

    I hope it's right.
    Last edited: Mar 26, 2012
  9. Mar 26, 2012 #8


    Actually you should probably use [itex] k_{2}[/itex] to establish the final epsilon then use [itex] k_{0}= max(k_1,k_2)[/itex]
    Last edited: Mar 26, 2012
  10. Mar 29, 2012 #9
    Something seemed fishy to me, so I went back to this and found a mistake. I need your help to see if what I have done this time is correct and legal.

    I'll start from the top again.

    -- Show that [itex]x(k)[/itex] goes to zero in the limit.

    Let [itex]ϵ>0[/itex]. Now, we know that [itex]0.5k[/itex] and [itex]u(k)[/itex] both go to zero(by assumption), therefore, for all [itex]ϵ_{1}>0[/itex], there exists [itex]k_{1}>0[/itex], such that if [itex]k>k_{1}[/itex], then [itex]|0.5k|<ϵ_{1}[/itex] and [itex]|u(k)|<ϵ_{1}[/itex]. Now, let [itex]k > 2k_{1} +1 [/itex]...

    [itex] | x(k) | = | 0.5^{k} x(0) + \sum_{i=0}^{k-1} 0.5^{i} u(k-i)| [/itex]
    [itex] = | 0.5^{k} x(0) + \sum_{i=0}^{k_{1}} 0.5^{i} u(k-i) + \sum_{i=k_{1}+1}^{k} 0.5^{i}u(k-i) | [/itex]

    The reason I did this is because in the sums, the u(k-i) goes backwards. So you can go [itex]k-k_{1}[/itex] steps back after which [itex] u(k-i) < \epsilon_{1} [/itex] is no longer true. Therefore

    [itex] |x(k)| < | \epsilon_{1} x(0) + \sum_{i=0}^{k_{1}} 0.5^{i} \epsilon_{1} + \sum_{i=k_{1}+1}^{k} 0.5^{i} u(k-i) | [/itex]

    Now, over k_{1}+1 to k, u(k-i) has a max value. Let [itex] M [/itex] be that max value. Then

    [itex] |x(k)| < | \epsilon_{1} x(0) + \sum_{i=0}^{k_{1}} 0.5^{i} \epsilon_{1} + \sum_{i=k_{1}+1}^{k} 0.5^{i} M | [/itex]

    Now, using the geometric series formula, I get

    [itex] |x(k)| < | \epsilon_{1} x(0) + \sum_{i=0}^{k_{1}} 0.5^{i} \epsilon_{1} + \frac{M 0.5^{k_{1}+1}}{0.5} + \frac{M 0.5^{k}}{0.5}| [/itex]

    [itex] |x(k)| < | \epsilon_{1} x(0) + \sum_{i=0}^{k_{1}} 0.5^{i} \epsilon_{1} + \frac{M \epsilon_{1}}{0.5} + \frac{M 0.5^{k}}{0.5}| [/itex]

    Now, for any [itex]\epsilon > 0[/itex] we need to find a [itex]k_{2}[/itex] such that [itex]k > k_{2}[/itex] would give

    [itex] | \epsilon_{1} x(0) |+ |\sum_{i=0}^{k_{1}} 0.5^{i} \epsilon_{1}| + |\frac{M 0.5^{k_{1}+1}}{0.5}| + |\frac{M 0.5^{k}}{0.5}| < \epsilon [/itex]

    [itex]0.5^{k} < \frac{0.5}{|M|}(\epsilon -| \epsilon_{1} x(0) |- |\sum_{i=0}^{k_{1}} 0.5^{i} \epsilon_{1}| - |\frac{M \epsilon_{1}}{0.5}|)[/itex]

    [itex] k = k_{2} > log(\frac{0.5}{|M|}(\epsilon -| \epsilon_{1} x(0) |- |\sum_{i=0}^{k_{1}} 0.5^{i} \epsilon_{1}| - |\frac{M \epsilon_{1}}{0.5}|))/log(0.5)[/itex] (since log(0.5) is negative)

    Now, for any [itex] \epsilon > 0 [/itex], pick [itex]k = max(2k_{1}+1, k_{2}) [/itex]. Then

    [itex] |x(k+1)| < \epsilon [/itex]

    If someone could check this and give some feedback, I would appreciate it a lot. Thanks!
    Last edited: Mar 29, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook