On identities of ruggles, horadam, howard, and young

Ruggles (1963) discovered that for integers n ≥ 0 and k ≥ 1 Fn+2k = LkFn+k + (-1)k+1Fn: Horadam (1965), Howard (2001), and Young (2003) each expanded this identity to generalized linear recurrence relations of orders 2, 3, and integers r ≥ 2, respectively. In this paper we let r ≥ 2 be an integer and w0, w1,...., wr-1, and p1, p2, ...., pr ≠ 0 be integers. For n > r set wn = p1wn-1 + p2wn-2 + ..... + prwn-r: We Find identities like those of Ruggles, Horadam, Howard, and Young, of the form wn+rk = Rk(r - 1; r)wn+(r-1)k + Rk(r - 2; r)wn+(r-2)k + .... + Rk(1; r)wn+k + Rk(0; r)wn; where, by a result of Young, Rk(i; r) is a linear recurrence relation of order (r i ) for i = 0; 1; ... ; r - 1. Our proof uses the Cayley-Hamilton theorem. Next, we Find the recurrences Rk(0; r) and Rk(r-1; r) for arbitrary r. Finally, we explicitly Find identities for orders r = 3, r = 4 and r = 5.