Solutions for General Recurrence Relations
Leonard E. Fuller · The Fibonacci Quarterly · 1981
In a recent article [1], the author obtained representations for the solutions of certain r9s. recurrence relations. In this paper we shall give representations for the solutions of general recurrence relations. In Section 4 we shall show that the results in[l] are a special case of the results of Sections 2 and 3 of this paper. We first of all characterize all decompositions of an integer n9 restricted to the first m positive integers. We define a multinomial from this that satisfies an mth-order recurrence relation with special initial conditions. Next the set of m positive integers is restricted to a subset A containing m9 and a second multinomial that satisfies a recurrence relation with special initial conditions is defined. In Section 3, we obtain solutions for comparable recurrence relations with general initial conditions. The final result gives us a solution for the general recurrence relations Hp = raiHp_ai + •- • +ratHp_at; HQ,..., E^at arbitrary. 2, BASIC m£h-0RVER RECURRENCE RELATIONS One of the classic concepts in the theory of numbers is that of partitions of the positive integers. One of the subcases considered is for the component integers to be the set of integers from 1 torn, In this case we denote the set of all partitions of n as P(n;m). The number of elements in this set is Pm (n). A given partition can be characterized by a set of integers k{. That is, n = 1/C-L +... + mkm. The integers k ^ are referred to as the frequency of £ in the given partitions. We refer to this given partition as p(k9n; m). For a given p(k9n; m) 9 we can represent n as a sum of integers from 1 to m i n (k.L + ••• +km)l k \\... km\\ ways. Each such representation is called a "decomposition of n " (some authors call them "compositions"). We denote this expression as dm(k,n). It is the number of decompositions of the partition p(k, n; m). This expression has a property that we shall find useful: (kx + •• • + k„) \\ (fcj. + •• • + km- 1)! m