Subject: discrete mathematics

the level of the question - college
who is asking the question - student

Hi! I'm having a lot of trouble with this question.

A sequence c is defined recursively as follows:

c0 = 2
c1 = 4
c2 = 6

ck= 5ck-3 for all integers

Prove that cn is even for all integers.

This is what I have done so far:

Let n=k where k belongs to all integers
ck=5ck-3 (Induction Hypothesis)
Let n=k+1
ck+ck+1=5ck-2 (by Induction Hypothesis)

This is where I am stuck...I'm not sure.. I might actually be going about this problem completely wrong since it says that you need to prove cn is even.

Can you help me? =/ Thank you very much!!


We think that you may be reading the question incorrectly. You are to show that cn is even for all integers where

c0 = 2
c1 = 4
c2 = 6
and for all k larger than or equal to 3,
ck = 5 ck-3

You are probably best to use "Strong Induction" for this sequence. In this case, your induction hypothesis should read:

"assume ck is even for all natural numbers k such that 0< = k < n"

Your final step is to show that cn is even using the definition of the sequence, i.e.

If n >= 3, cn = 5cn-3 will be even because cn-3 will be even by our induction hypothesis.

Your basic step took care of the case where n = 0, 1 and 2 and we have successfully proved the result is true for all n >= 3.

Hope this helps,
Leeanne and Penny
Go to Math Central