Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction for polynomial/sequence proof

  1. Sep 4, 2010 #1
    1. The problem statement, all variables and given/known data
    Let k be a natural number, and r a real number with |r|<1. Prove (by induction on k) that for any polynomial P of degree k, there is a polynomial Q of degree k with Q(n+1)r^(n+1) - Q(n)r^n = P(n)r^n
    Hint: consider differences of successive terms for (n^k)(r^n) and use the inductive hypothesis

    3. The attempt at a solution

    Base case: degree 0

    a_0 r^n = b_0 r^(n+1) - b_0 r^n

    Is it ok to just rearrange this, and find b_0 in terms of a_n, r^n etc..

    a_0/(r-1) = b_0

    So for some polynomial of degree 0 I can always find another using the fact that b_0 = a_0/(r-1). However, when I try to do this with higher degrees, I get the coefficients in terms of n which means that the polynomial depends on what n is which means I'm not proving I can find one that satisfies for all n. Any ideas?
  2. jcsd
  3. Sep 4, 2010 #2


    User Avatar
    Science Advisor

    What, exactly, are you trying to prove? That, for a given polynomial, P, and a given specific number, r, there is a polynomial, Q, such that Q(n+1)r^(n+1) - Q(n)r^n = P(n)r^n? But what does "Q(n+1)" mean? The polynomial, Q(x), evaluated at x= n+ 1? Yes, if P is a constant, P(x)= a_0 for all x, then we have Q(1)r- Q(0)= P(0). But Q now does not have to be a constant. Either Q(1)= (P(0)+ Q(0))/r or Q(1)= 0 and Q(0)= -P(0).
  4. Sep 4, 2010 #3
    Just wondering, why did you evaluate the Q(n+1) - Q(n) at n=1? I dont see how this helps. The base case is degree k = 0 which is constant polynomials... rather than n = 0. Am I missing something here?

    Also, Q must be a constant polynomial also because it must be the same degree as P.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook