# Rational Divide-and-Conquer Relations

Authors: Charinthip Hengkrawit; Vichian Laohakosol; Watcharapon Pimsert
Journal: ISRN Mathematical Analysis
 (2011)

---

## Abstract

A rational divide-and-conquer relation, which is a natural generalization of the classical divide-and-conquer relation, is a recursive equation of the formf(bn)=R(f(n),f(n),…,f(b−1)n)+g(n), where b is a positive integer ≥2;
R a rational function in b−1 variables and g a given function. Closed-form solutions of certain rational divide-and-conquer relations which can be used to characterize the trigonometric cotangent-tangent and the hyperbolic cotangent-tangent function solutions are derived and their global behaviors are investigated.


---

## Body

## 1. Introduction

The classical divide-and-conquer relation is a recursive relation of the form ([1–3])
(1.1)F(n)=aF(nb)+G(n),
where a,b(≥2) are positive integers and G(n) is a given function. This class of recurrence relations arises frequently in the analysis of recursive computer algorithms. Such algorithms split a problem of size n into a subproblems each of size [n/b], with G(n) extra operations being required when this split of a problem of size n into smaller problems is made. Although, there are certain cases, see for example the table on page 273 of [3], where the relation (1.1) can be solved explicitly, it is generally impossible to solve (1.1) for all values of n. However, when a starting value F(bλ) is given, a solution for n=bk(k>λ) can be found by making a change of variables  F(bk)=ϕ(k) which turns (1.1) into a first order difference equation of the form ([1, page 137])
(1.2)ϕ(k)=aϕ(k-1)+G(bk),
and this last recursive equation can be easily solved. Another aspect of importance in the study of divide-and-conquer relations deals with the size of F(n) which is used in analyzing the complexity of corresponding divide-and-conquer algorithms ([2, Section 5.3]).Generalizing the above notion, by arational divide-and-conquer (RDAC) relation, we refer to a recursive relation of the form
(1.3)f(bn)=R(f(n),f(2n),…,f(b-1)n)+g(n),
where b∈ℕ,b≥2,R(x1,…,xb-1) a rational function in x1,…,xb-1, and g(n) a given function. Here we aim to find explicit closed form solutions of certain nonlinear divide-and-conquer relations which is closely related to identities of the trigonometric and hyperbolic cotangent identities. Our investigation arises from an observation that the trigonometric cotangent function satisfies, among a number of other identities, the following identity:
(1.4)cot(3A)=cot⁡2Acot⁡A-1cot⁡2A+cot⁡A,
which leads to an RDAC relation of the form
(1.5)x3n=x2nxn-1x2n+xn.
This relation can be rewritten as
(1.6)x3n-ix3n+i=(xn-ixn+i)(x2n-ix2n+i)(i=-1),
which is a simpler looking RDAC relation of the form
(1.7)U3n=UnU2n(Un:=xn-ixn+i)
that can be immediately solved. Let us mention in passing that similar substitution techniques have been employed earlier in [4, 5].Our first objective here is to find, in the next section, a closed form solution of(1.8)Ubn=Unα1U2nα2⋯U(b-1)nαb-1,
an RDAC relation generalizing (1.7). Experiences from (1.7) with the cotangent function lead us to apply the results from our first objective to use such RDAC relations to characterize the trigonometric and hyperbolic tangent and cotangent functions, and this will be carried out in the following section as applications.


## 2. Closed Form Solutions

Before stating our main result, it is convenient to introduce a new notation. Fork∈ℕ, let us write
(2.1)(α1Vl+α2V2l+⋯+αb-1V(b-1)l)*k=∑i1+i2+⋯+ib-1=k(ki1,i2,…,ib-1)α1i1α2i2⋯αb-1ib-1V1i12i2⋯(b-1)ib-1l,
where (ki1,i2,…,ib-1):=k!/i1!i2!⋯ib-1! denote the customary multinomial coefficients. Our main result is:Theorem 2.1.
Letb∈ℕ,b≥2, and α1,…,αb-1∈ℝ. If the sequence {Un}n≥0 satisfies the RDAC relation
(2.2)Ubn=Unα1U2nα2⋯U(b-1)nαb-1(n≥1),
then for ℓ≢0(modb), one has
(2.3)Ubkl∏i1+i2+⋯+ib-1=lU1i12i2⋯(b-1)ib-1l(ki1,i2,…,ib-1)α1i1α2i2⋯αb-1ib-1(k∈N).Proof.
Taking principal logarithms of (2.2), the relation becomes
(2.4)Vbn=α1Vn+α2V2n+⋯+αb-1V(b-1)n(n≥1),
where Vi=logUi. For ℓ≢0(modb), evaluating (2.4) at n=bℓ, we get
(2.5)Vb2l=α1Vbl+α2Vb2l+⋯+αb-1Vb(b-1)l=α1(α1Vl+α2V2l+⋯+αb-1V(b-1)l)+α2(α1V2l+α2V22l+⋯+αb-1V2(b-1)l)+⋯+αb-1(α1V(b-1)l+α2V2(b-1)l+⋯+αb-1V(b-1)2l)=α12Vl+α22V22l+⋯+αb-12V(b-1)2l+2α1α2V2l+⋯+2αiαjVijl+⋯+2αb-2αb-1V(b-2)(b-1)l.
Using the notation introduced above, we see at once that
(2.6)Vbl=(α1Vl+α2V2l+⋯+αb-1V(b-1)l)*1Vb2l=(α1Vl+α2V2l+⋯+αb-1V(b-1)l)*2.
To finish the proof, we need only show that for all k∈ℕ(2.7)Vbkl=(α1Vl+α2V2l+⋯+αb-1V(b-1)l)*k.
We proceed by induction. For any ℓ≢0(modb), assume that (2.7) holds up to k. Thus, by (2.4) and the induction hypothesis one has
(2.8)Vbk+1l=α1Vbkl+α2Vbk2l+⋯+αb-1Vbk(b-1)l=α1(α1Vl+α2V2l+⋯+αb-1V(b-1)l)*k+α2(α1V2l+α2V22l+⋯+αb-1V2(b-1)l)*k+⋯+αb-1(α1V(b-1)l+α2V2(b-1)l+⋯+αb-1V(b-1)2l)*k=α1∑i1+i2+⋯+ib-1=k(ki1,i2,…,ib-1)α1i1α2i2⋯αb-1ib-1V1i12i2⋯(b-1)ib-1l+α2∑i1+i2+⋯+ib-1=k(ki1,i2,…,ib-1)α1i1α2i2⋯αb-1ib-1V(1i12)(2i22)⋯((b-1)ib-12)l+⋯+αb-1∑i1+i2+⋯+ib-1=k(ki1,i2,…,ib-1)α1i1α2i2⋯αb-1ib-1V(1i1(b-1))(2i2(b-1))⋯(b-1)ib-1+1l=∑i1+i2+⋯+ib-1=k+1(ki1,i2,…,ib-1)α1i1α2i2⋯αb-1ib-1V1i12i2⋯(b-1)ib-1l.The casesb=2 and 3 are of particular interest and we record them here for future reference.Corollary 2.2.
(I) Letα∈ℝ. If the sequence {Un}n≥0 satisfies the RDAC relation
(2.9)U2n=Unα(n≥1),
then for ℓ≢0(mod2), one has
(2.10)U2kl=Ulαk(k∈N).
(II) Letα1,α2∈ℝ. If the sequence {Un}n≥0 satisfies the RDAC relation
(2.11)U3n=Unα1U2nα2(n≥1),
then for ℓ≢0(mod3), one has
(2.12)U3kl=Ul(k0)α1kα20U2l(k1)α1k-1α2⋯U2kl(kk)α10α2k(k∈N).


## 3. Applications

We now apply the result of Theorem2.1 and Corollary 2.2 to several RDAC relations including those that can be used to characterize the trigonometric and hyperbolic tangent and cotangent functions.Proposition 3.1.
(I) Suppose that the sequence{xn}n≥0 satisfies an RDAC relation of the form
(3.1)x2n=xn2-12xn(n≥1).
For ℓ≢0(mod2) and k∈ℕ, if the condition 2kθℓ≢0(mod2π) is fulfilled, then
(3.2)x2kl=cot(-2kθl2)=cot(2karccotxl),
where
(3.3)θl=-2arccotxl.
(II) Assume that the sequence{xn}n≥0 satisfies an RDAC relation of the form
(3.4)x2n=2xn1-xn2(n≥0).
For ℓ≢0(mod2) and k∈ℕ, if 2kθℓ is not an odd multiple of π, then
(3.5)x2kl=tan⁡(-2kθl2)=tan⁡(2karctan⁡xl),
where
(3.6)θl=-2arctanxl.
(III) If the sequence{xn}n≥0 satisfies
(3.7)x2n=xn2+12xn(n≥0),
then, for ℓ≢0(mod2), k∈ℕ, one has
(3.8)x2kl=coth⁡(-2kθl2)=coth⁡(2karccothxl),
where
(3.9)θl=-2arccothxl.
(IV) If the sequence{xn}n≥0 satisfies
(3.10)x2n=2xn1+xn2(n≥0),
then, for ℓ≢0(mod2), k∈ℕ, one has
(3.11)x2kl=tanh(-2kθl2)=tanh(2karctanhxl),
where
(3.12)θl=-2arctanhxl.Proof.
(I) As seen in Section1, the RDAC relation (3.1) is equivalent to
(3.13)U2n=Un2(Un=xn-ixn+i),
whose solution is, by virtue of Corollary 2.2, U2kℓ=Uℓ2k. Thus,
(3.14)x2kl-ix2kl+i=(xl-ixl+i)2k.
Setting eiθℓ=(xℓ-i)/(xℓ+i), one has
(3.15)x2kl=i(1+ei2kθl1-ei2kθl)=cot(-2kθl2)=cot(2karccotxl),
provided 2kθℓ≢0(mod2π).
(II) Substitutingxn by 1/xn turns (3.4) into (3.1) and so the result follows at once from part (I).
(III) Substitutingxn by ixn in (3.7) turns it into a rational recursive equation of the form (3.1) and so part (I) yields the desired result.
(IV) Replacingxn by ixn in (3.10), we get a rational recursive equation of the form (3.4) and part (II) yields the result.Remark 3.2.
Although the substitutionxn by 1/xn employed in part (II) of Proposition 3.1 allows us to obtain a closed form solution of the RDAC relation (3.4), there remains a difficulty should there exist integer N such that xN=0. To overcome this shortcoming, we may either interpret the infinite value of the two expressions on both sides of the solution as equal or repeat the technique used in the proof of Proposition 3.1 to solve (3.4).Proposition 3.3.
(I) Suppose that the sequence{xn}n≥0 satisfies an RDAC relation of the form
(3.16)x3n=x2nxn-1x2n+xn(n≥1).
For ℓ≢0(mod3) and k∈ℕ, if the condition
(3.17)(k0)θl+(k1)θ2l+⋯+(kk)θ2kl≢0(mod⁡2π)
is fulfilled, then
(3.18)x3kl=cot⁡(-(k0)θl-(k1)θ2l-⋯-(kk)θ2kl2)=cot⁡((k0)arccot⁡xl+(k1)arccot⁡x2l+⋯+(kk)arccot⁡x2kl),
where
(3.19)θj=-2arccot⁡xj(j∈{l,2l,…,2kl}).
(II) Assume that the sequence{xn}n≥0 satisfies an RDAC relation of the form
(3.20)x3n=xn+x2n1-xnx2n(n≥0).
For ℓ≢0(mod3) and k∈ℕ, if θℓ+(k1)θ2ℓ+⋯+(kk)θ2kℓ is not an odd multiple of π, then
(3.21)x3kl=tan(-(k0)θl-(k1)θ2l-⋯-(kk)θ2kl2)=tan((k0)arctanxl+(k1)arctanx2l+⋯+(kk)arctanx2kl),
where
(3.22)θj=-2arctanxj(j∈{l,2l,…,2kl}).
(III) If the sequence{xn}n≥0 satisfies
(3.23)x3n=xnx2n+1xn+x2n(n≥0),
then, for ℓ≢0(mod3),k∈ℕ, one has
(3.24)x3kl=coth⁡(-(k0)θl-(k1)θ2l-⋯-(kk)θ2kl2)=coth⁡((k0)arccoth⁡xl+(k1)arccoth⁡x2l+⋯+(kk)arccoth⁡x2kl),
where
(3.25)θj=-2arccoth⁡xj(j∈{l,2l,…,2kl}).
(IV) If the sequence{xn}n≥0 satisfies
(3.26)x3n=xn+x2n1+xnx2n(n≥0),
then, for ℓ≢0mod3, k∈ℕ, one has
(3.27)x3kl=tanh(-(k0)θl-(k1)θ2l-⋯-(kk)θ2kl2)=tanh((k0)arctanhxl+(k1)arctanhx2l+⋯+(kk)arctanhx2kl),
where
(3.28)θj=-2arctanhxj(j∈{l,2l,…,2kl}).Proof.
(I) As seen in Section1, the RDAC relation (3.16) is equivalent to
(3.29)U3n=UnU2n(Un=xn-ixn+i),
whose solution is, by virtue of Corollary 2.2, U3kℓ=Uℓ(k0)U2ℓ(k1)⋯U2kℓ(kk). Thus,
(3.30)x3kl-ix3kl+i=(xl-ixl+i)(k0)(x2l-ix2l+i)(k1)⋯(x2kl-ix2kl+i)(kk).
Setting eiθj=(xj-i)/(xj+i)(j∈{ℓ,2ℓ,…,2kℓ}), one has
(3.31)x3kl=i(1+ei((k0)θl+⋯+(kk)θ2kl)1-ei((k0)θl+⋯+(kk)θ2kl))=cot(-(k0)θl-⋯-(kk)θ2kl2)=cot⁡((k0)arccotxl+(k1)arccotx2l+⋯+(kk)arccotx2kl),
provided (k0)θℓ+⋯+(kk)θ2kℓ≢0(mod2π).
(II) Substitutingxn by 1/xn turns (3.20) into (3.16) and so the result follows at once from part (I).
(III) Substitutingxn by ixn in (3.23) turns it into a rational recursive equation of the form (3.16), and so part (I) yields the desired result.
(IV) Replacingxn by ixn in (3.26), we get a rational recursive equation of the form (3.20), and part (II) yields the result.Remark 3.4.
As in the remark following Proposition3.1, the substitution xn by 1/xn in part (II) causes no harm should there exists integer N such that xN=0 by either interpreting the infinite value of the expressions on both sides of the solution as equal. Alternately, we may repeat the technique used in the proof of Proposition 3.3 to solve (3.20).As for the case of generalb, an entirely analogous proof as that in Proposition 3.3, which we omit here, leads to Proposition 3.5.Proposition 3.5.
Letb∈ℕ,b≥2.
(I) Suppose that the sequence{xn}n≥0 satisfies an RDAC relation of the form
(3.32)xbn=x(b-1)nxn-1x(b-1)n+xn(n≥1).
For ℓ≢0(modb) and k∈ℕ, if the condition
(3.33)(k0)θl+(k1)θ(b-1)l+⋯+(kk)θ(b-1)kl≢0mod⁡2π
is fulfilled, then
(3.34)xbkl=cot⁡(-(k0)θl-(k1)θ(b-1)l-⋯-(kk)θ(b-1)kl2)=cot⁡((k0)arccot⁡xl+(k1)arccot⁡x(b-1)l+⋯+(kk)arccot⁡x(b-1)kl),
where
(3.35)θj=-2arccot⁡xj(j∈{l,(b-1)l,…,(b-1)kl}).
(II) Assume that the sequence{xn}n≥0 satisfies an RDAC relation of the form
(3.36)xbn=xn+x(b-1)n1-xnx(b-1)n(n≥0).
For ℓ≢0(modb) and k∈ℕ, if θℓ+(k1)θ(b-1)ℓ+⋯+(kk)θ(b-1)kℓ is not an odd multiple of π, then
(3.37)xbkl=tan(-(k0)θl-(k1)θ(b-1)l-⋯-(kk)θ(b-1)kl2)=tan((k0)arctanxl+(k1)arctanx(b-1)l+⋯+(kk)arctanx(b-1)kl),
where
(3.38)θj=-2arctanxj(j∈{l,(b-1)l,…,(b-1)kl}).
(III) If the sequence{xn}n≥0 satisfies
(3.39)xbn=xnx(b-1)n+1xn+x(b-1)n(n≥0),
then, for ℓ≢0(modb), k∈ℕ, one has
(3.40)xbkl=coth⁡(-(k0)θl-(k1)θ(b-1)l-⋯-(kk)θ(b-1)kl2)=coth⁡((k0)arccoth⁡xl+(k1)arccoth⁡x(b-1)l+⋯+(kk)arccoth⁡x(b-1)kl),
where
(3.41)θj=-2arccoth⁡xj(j∈{l,(b-1)l,…,(b-1)kl}).
(IV) If the sequence{xn}n≥0 satisfies
(3.42)xbn=xn+x(b-1)n1+xnx(b-1)n(n≥0),
then, for ℓ≢0(modb), k∈ℕ, one has
(3.43)xbkl=tanh(-(k0)θl-(k1)θ(b-1)l-⋯-(kk)θ(b-1)kl2)=tanh((k0)arctanhxl+(k1)arctanhx(b-1)l+⋯+(kk)arctanhx(b-1)kl),
where
(3.44)θj=-2arctanhxj(j∈{l,(b-1)l,…,(b-1)kl}).When all the exponentsαj in (2.2) are equal to 1, RDAC relations, even more general than those in Proposition 3.5 which can be explicitly solved by our device, are given in the next proposition.Proposition 3.6.
Letb∈ℕ,  b≥2,  w∈ℂ∖{0}. If the sequence {xn}n≥0 satisfies
(3.45)xbnw=(xn+w)(x2n+w)⋯(x(b-1)n+w)+(xn-w)(x2n-w)⋯(x(b-1)n-w)(xn+w)(x2n+w)⋯(x(b-1)n+w)-(xn-w)(x2n-w)⋯(x(b-1)n-w),
then for ℓ≢0(modb)  and k∈ℕ one has
(3.46)xbkl=w(A++A-A+-A-),
provided the values exist, where
(3.47)A+:=∏i1+i2+⋯+ib-1=l(x1i12i2⋯(b-1)ib-1l+w)(ki1,i2,…,ib-1)A-:=∏i1+i2+⋯+ib-1=l(x1i12i2⋯(b-1)ib-1l-w)(ki1,i2,…,ib-1).Proof.
Rewriting (3.45), we get
(3.48)xbn-wxbn+w=(xn-wxn+w)(x2n-wx2n+w)⋯(x(b-1)n-wx(b-1)n+w)
or
(3.49)Ubn=UnU2n⋯U(b-1)n(Uj=xj-wxj+w,j∈{n,2n,…,(b-1)n}).
Theorem 2.1 thus yields for ℓ≢0(modb) and k∈ℕ(3.50)Ubkl=∏i1+i2+⋯+ib-1=lU1i12i2⋯(b-1)ib-1l(ki1,i2,…,ib-1),
that is,
(3.51)xbkl-wxbkl+w=∏i1+i2+⋯+ib-1=l(x1i12i2⋯(b-1)ib-1l-wx1i12i2⋯(b-1)ib-1l+w)(ki1,i2,…,ib-1),
and the result follows.


## 4. Global Behaviors

It is often desirable to know about global behaviors of the solutions of recursive equations, such as those in [6]. Using the explicit forms found above, this question is easily solved for RDAC relations in Proposition 3.5 with b=2.Proposition 4.1.
Let the notation be as in Proposition3.1.
(I) Suppose that the sequence{xn}n≥0 satisfies an RDAC relation of the form
(4.1)x2n=xn2-12xn(n≥1).
For each fixed ℓ≢0(mod2) and k∈ℕ,  (a)
ifθℓ is a rational multiple of π, then either {x2kℓ}k∈ℕ diverges in finitely many steps or {x2kℓ} is periodic;(b)
ifθℓ is not a rational multiple of π, then x2kℓ exists for all k∈ℕ and the sequence {x2kℓ}k∈ℕ is never periodic.
(II) Suppose that the sequence{xn}n≥0 satisfies an RDAC relation of the form
(4.2)x2n=2xn1-xn2(n≥0).
For each fixed ℓ≢0(mod2),  (a)
ifθℓ is a rational multiple of π, then either {x2kℓ}k∈ℕ diverges in finitely many steps or {x2kℓ} is periodic;(b)
ifθℓ is not a rational multiple of π, then x2kℓ exists for all k∈ℕ and the sequence {x2kℓ}k∈ℕ is never periodic.
(III) Suppose that the sequence{xn}n≥0 satisfies
(4.3)x2n=xn2+12xn(n≥0).
For each fixed ℓ≢0(mod2), (a)
ifθℓ=0, then the sequence {x2kℓ}k≥1 does not exist;(b)
ifθℓ>0, the sequence {x2kℓ} is strictly decreasing in the interval [coth(θℓ),1);(c)
ifθℓ<0, then {x2kℓ}k≥1 is strictly increasing in the interval [coth(θℓ),-1).
(IV) Suppose that the sequence{xn}n≥0 satisfies
(4.4)x2n=2xn1+xn2(n≥0).
For each fixed ℓ≢0(mod2),(z)
ifθℓ=0, then {x2kℓ}k∈ℕ is the zero sequence;(b)
ifθℓ>0, then the sequence {x2kℓ} is strictly increasing in [tanh(θℓ),1);(c)
ifθℓ<0, the sequence is strictly decreasing in [tanh(θℓ),-1).Proof.
(I) From part (I) of Proposition3.1, we know that
(4.5)x2kl=cot(-2k-1θl)
provided 2kθℓ≢0(mod2π). Consider the case where θℓ is a rational multiple of π, say,
(4.6)θl=mπtwithm,t(>0)∈Z,gcd(m,t)=1.
If t is a multiple of 2, then it is easily checked that {x2kℓ}k∈ℕ diverges in finitely many steps. If t≥2 is not a multiple of 2, let t=2vT, where 2v∣∣t,T≥3. Observe that for all large n∈ℕ, when evaluating the values of cotangent, we need only look at
(4.7)2nθl=2nmπt=2n-vmπT(mod⁡2π),
which is equivalent to looking at
(4.8)Gn:=2n-vm(mod⁡2T).
Since each Gn takes at most 2T values and the sequence {x2kℓ}k∈ℕ is infinite, there are positive integers N1<N2 such that GN1=GN2, which in turn implies that {x2kℓ}k∈ℕ is periodic.
Finally, ifθℓ is not a rational multiple of π, then 2k-1θℓ is not a multiple of π showing that the sequence {x2kℓ}k∈ℕ is well defined and never periodic.
The proof of part (II) is similar to that of part (I).
(III) Ifθℓ=0, then the values x2kℓ=coth(2kθℓ) become infinite for all k∈ℕ and part (a) follows. Since x2kℓ=coth(2kθℓ) is a strictly decreasing (resp. increasing) function of k according as θℓ>0 (resp. θℓ<0), the results in (b) and (c) are immediate.
(IV) Ifθℓ=0, then x2kℓ=tanh(θℓ)=0. Arguments for the other two cases θℓ>0 and θℓ<0 are similar to those in part (III).Note from Proposition4.1 that global behaviors of solutions in the case b=2 depend solely on the single value θℓ. The situation when b≥3 is more complex since their global behaviors depend heavily on the variable k as we see in the following illustration. Keeping the notation of Proposition 3.5, suppose that the sequence {xn}n≥0 satisfies an RDAC relation of the form
(4.9)xbn=x(b-1)nxn-1x(b-1)n+xn(n≥1).
From part (I) of Proposition 3.5, we know that
(4.10)xbkl=cot(-(k0)θl-(k1)θ(b-1)l-⋯-(kk)θ(b-1)kl2).
This explicit form shows that, for each fixed ℓ≢0(modb), the behavior of xbkℓ considered as a function of k∈ℕ depends on all θℓ,…,θ(b-1)kℓ, and we can merely infer that the values xbkℓ are  well defined (i.e., finite) if and only if
(4.11)(k0)θl+(k1)θ(b-1)l+⋯+(kk)θ(b-1)kl≢(mod⁡2π).



---

*Source: 908508-2011-01-02.xml*