Bounding ( ( 2 d − 1 ) n − 1 n − 1 ) Claim: ( 3 n − 1 n − 1 ) ≤ 6.25 n 1. Why?2. Can the proof be extended to obtain a bound on ( ( 2 d − 1 ) n − 1 n − 1 ) , with the bound being f ( d ) n for some function f?

Question

Bounding                               (                                      (          2          d          −          1          )          n          −          1                          n          −          1                                      )                    Claim:                               (                                      3          n          −          1                          n          −          1                                      )                      ≤      6.25    n  1. Why?2. Can the proof be extended to obtain a bound on                               (                                      (          2          d          −          1          )          n          −          1                          n          −          1                                      )                    , with the bound being   f  (  d      )    n   for some function   f?

Sean Sutton · Accepted Answer

First, lets bound things as easily as possible. Consider the inequality                    (                    n      k                      )              =            (      n      −      k      )      !              k      !        ≤            n              k                    k      !        ≤      e          k                  (              n        k            )              k        .The 𝑛𝑘 comes from the fact that 𝑛 is bigger then each factor of the product in the numerator. Also, we know that   k  !      e    k    &amp;gt;      k    k   by looking at the       k          t      h       term in the Taylor series, as       e    k    =  1  +  k  +  ⋯  +            k      k              k      !        +  ⋯Now, lets look at the similar   3  n and   n instead of   3  n  −  1 and   n  −  1. Then we see that                    (                            3        n            n                      )              ≤      e          n                  (      3      )              n        ≤            (      8.15      )              n      and then for any   k we would have                    (                            k        n            n                      )              ≤            (      k      e      )              n        .                    (                            (        k        +        1        )        n            n                      )              ≤            (                        (          k          +          1                      )                          k              +              1                                                k          k                    )        n    .Notice that when   k  =  2 we have   27      /    4 which is   6.25

Bounding ((2d−1)n−1 n−1) Claim: (3n−1 n−1)<=6.25n 1. Why? 2. Can the proof be extended to obtain a bound on ((2d−1)n−1n−1), with the bound being f(d)n for some function f?

Answered question

Answer & Explanation

New Questions in Precalculus