When Is a Definition Not a Definition?

(New Question of the Week)

From time to time a student will ask for help understanding what he reads in his textbook. This often requires some back-and-forth as we try to understand both what the textbook is saying in its context (without having a copy of it to look at), and how the student is misunderstanding it. This difficulty is compounded by the fact that authors often differ somewhat in their definitions, and that in fact definitions often vary according to their contexts. What follows is an example of all of these dynamics, giving some insights into both how communication works under less than ideal circumstances, how to read a textbook, and what constitutes a definition.

Clarifying the question

Last month Bhaskar, a college student taking a course in Discrete Mathematics, asked this:

Sir, is the Tower Of Hanoi’s recurrence relation, i.e. n=(n-1) + 1, a Linear Recurrence Relation?

Sir, I am confused because in my book the definition of Linear Recurrence Relation is, When in any recurrence relation the right hand side is a sum of previous terms of the sequence each multiplied by a function of n.

It says:

A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form

\(a_n = c_1 a_{n-1} + c_2 a_{n-2} + … + c_k a_{n-k}\)

where \(c_1, c_2, …, c_k\) are real numbers, and \(c_k \ne 0\)

The recurrence relation in the definition is linear because the right-hand side is a sum of previous terms of the sequence each multiplied by a function of n. …

First, we had to clarify what the recurrence relation was that he intended, because it had been typed incorrectly. It was, as I expected, T_n = 2T_n-1 + 1, meaning that the nth term in the sequence is 1 more than twice the previous term.  (If you are unfamiliar with the Tower of Hanoi problem, see our FAQ on the subject, and this question about its recurrence relation.) But then, it was not clear to me where he saw a conflict with the book’s definition. I wondered if it was that the coefficients are constants, not explicitly functions of n; so I asked,

Please tell us why you think the recurrence relation does not fit the definition of a linear recurrence.

Are you perhaps thinking that a constant is not a function of n? It is, just as f(x) = 1 is a function of x.

Bhaskar replied that he felt that the last sentence he had quoted, “The recurrence relation in the definition is linear because the right-hand side is a sum of previous terms of the sequence each multiplied by a function of n“, is an incomplete definition. This was still unclear to me, so I asked specifically what he felt was missing, and he replied,

According to me, this should be a correct definition of Linear Recurrence Relation:

The recurrence relation in which the right hand side is a sum of previous terms of the sequence each multiplied by a function of n and functions of n.

I still didn’t get it. Finally, he said this:

I am confused because according to my book the definition of Linear Recurrence Relation is “When in any recurrence relation the right hand side is a sum of previous terms of the sequence each multiplied by a function of n. is called Linear Recurrence Relation.”

If I follow that definition, then T_n = 2T_n-1 + 1 is not a Linear Recurrence Relation, isn’t it?

I am telling the reason why “According to the definition there should be only those terms that are sum of previous terms of the sequence, but here we also have a term which is a function of n and that term is 1.”

Finally I saw the point that I should have seen from the start: It was the last term, 1, that he was concerned about, because it is not a multiple of a previous term, but a pure constant. Now I could look back at everything he had written and follow his thinking from the start. His error was to take a comment that applied an (unstated) definition to a specific example (“this is linear because …”), and treat it as a complete definition (“when … it is called linear”). He was exactly right: What he took to be the definition was in fact incomplete.

Explaining the textbook

I replied,

I apologize – I finally see your point; I was focusing my attention on the wrong parts of what you said. You are saying that not all terms in the RHS are multiples of terms of the sequence, since one of them is a constant, not multiplying a term. This is called a non-homogeneous recurrence. That does not make it nonlinear.

The definition they give is

A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form

a_n = c₁a_n-1 + c₂a_n-2 + … + c_ka_n-k,

where c₁, c_2, …, c_k are real numbers, and c_k ≠ 0.

This does not define what linear means; it just defines the entire phrase. But they then explain, without quoting a definition, why the word “linear” is appropriate:

The recurrence relation in the definition is linear because the right-hand side is a sum of previous terms of the sequence each multiplied by a function of n.

Do you see that this is not actually a definition, just an application of a definition? It does not tell you what does not constitute a linear recurrence, only the feature of this one that does make it linear. It does not say that a linear recurrence can only have such terms.

Do they ever actually give a definition of “linear recurrence relation”?

A difficulty I have had in searching for references to give you, is that many discussions of linear recurrence relations fail to mention explicitly that the definition they give applies only to the homogenous case, so it is easy to find definitions that appear to support your impression of what your book says. But in fact, the definition you said you think is correct is (when I add punctuation to prevent my misreading it as I did) exactly correct:

A Linear Recurrence Relation is a recurrence relation in which the right hand side is a sum of previous terms of the sequence each multiplied by a function of n, and (possibly) a function of n alone.

To make sure this is clear, here is what I am saying:

1. What the book says in explaining the word “linear” is just that if the expression consists of multiples of previous terms of the sequence, then it is called linear. This is only half of a definition; a definition is not just a unidirectional conditional statement; it must also tell you what does not fit the definition — it must give necessary and sufficient conditions for the defined entity. We can’t infer from what was said that a recurrence relation is linear only if each term is a multiple of a previous term in the sequence, or, equivalently, that if the fact they point out is not true, then the recurrence is not linear.
2. In fact, the recurrence relation Bhaskar asked about is not the type being defined on this page; it is not a linear homogeneous recurrence relation, but a linear non-homogeneous recurrence relation. And what makes it non-homogeneous is exactly what he was asking about: the fact that one term in the expression is not a multiple of a previous term of the sequence.
3. The full definition of “linear”, in the context of both homogeneous and non-homogeneous recurrence relations, is what Bhaskar suggested, though it may not be given in his textbook.

The important of context

Early in our discussion, I looked for sources to refer Bhaskar to, that would clarify the definition he was looking for. Part of the reason it took me so long to figure out what the real issue was, is that I confused myself by finding only definitions that were not helpful. (Meanwhile, another Math Doctor, who is more familiar with the topic, was struggling with technical issues that prevented him from giving an answer that probably would have been more immediately helpful.)

Here are two references I eventually found that include the definition Bhaskar needed (though even these only cover the constant-coefficient case):

Linear recurrence relations with constant coefficients

Solving Linear Recurrence Relations, Niloufar Shafiei (see page 24)

The former starts,

Recall that a linear recurrence relation with constant coefficients c₁, c_2, …, c_k (c_k ≠ 0)
of degree k and with control term F(n) has the form

a_n = c₁a_n-1 + c₂a_n-2 + … + c_ka_n-k + F(n)    (n ≥ k).

But many sources define only the homogeneous case, without mentioning that there is a more general case. For example, in this page,

Linear Recurrence Relations, Brilliant

we read

A linear recurrence relation is an equation that defines the nth term in a sequence in terms of the  previous terms in the sequence. The recurrence relation is in the form:

x_n = c₁x_n-1 + c₂x_n-2 + … + c_kx_n-k

where each c_i is a constant coefficient.

This isn’t technically an error; the authors are just dealing with a particular context (homogeneous recurrence relations), within which what they say is correct. But if we go to this source without realizing that our context is different from theirs, we will get confused, just as Bhaskar did in considering an example that did not fit the context of his textbook page.

I haven’t had occasion to see whether Bhaskar’s textbook ever does give explicit definitions, or clarify the details that caused confusion here. But it is clear that we have to be careful in reading textbooks or online sources, not to read too much into what is said, and not to assume that the context of every source we find is identical to our own context. Mathematicians are generally very careful to say exactly what they mean, but humans (including mathematicians!) have a natural tendency to read something other than what is said!