# Can you give an inductive definition to define the length of a list L?

Having trouble understanding what it means to define something inductively in the following context.

Can you give an inductive to define the length of a list L?

a. The total number of items in L is the length of L

b. Basis: the length of an empty list is 0 Induction: the length of a list is 2*(length of half the list)

c. Basis: the length of an empty list is 0 Induction: the length of a list is (length of head(list))+(length of tail(list))

d. Basis: the length of an empty list is 0 Induction: the length of a list is 1+(length of tail(list))

The answer is (d). Why might this be?

And also for this similar question:

Can you give an inductive definition to define what it means for an element X to be a member of a list L?

a. X is a member of a list L if and only if X belongs to the list L.

b. X is a member of a list L if either X is the head of the list or X is a member of the tail of L.

c. X is a member of a list L if we can find an element Y in L and X=Y.

d. X is a member of a list L if we can find an element Y in the tail of L

Thank you.

• A multiple choice question beginning with "can you..." should have two possible answers: yes and no.
– Kai
May 10 '17 at 9:40

In an inductive definition what you have to do is to find a base case and the inductive step.

In your case, suppose to have a list $L$ and let head be the first element and tail the rest of the list.

For example, if $L=[1,2,3,4,5]$:

• head = $1$
• tail = $[2,3,4,5]$

In order to understand the meaning you could consider writing a recursive function to compute the length of the list.

• Basis: the length of an empty list is 0
• Induction: the length of a list is 1+(length of tail(list))

This corresponds to the recursive function

function len(list L)
if L is empty
return 0
else return 1 + len(tail(L))


Same for the second question:

function member(elem x, list L)
if L is empty
return false
return true
else return member(x, tail(L))


and this corresponds to say: X is a member of a list L if either

• X is the head of the list or
• X is a member of the tail of L.