# How to prove that $X_n\equiv 1\pmod 3$

The question states:

Consider the following defined on the natural numbers :$$X_k = 1$$ for $$1\le k \le4$$ $$X_k = (X_{k-1} + X_{k-2} + X_{k-3} + X_{k-4})$$

Prove by mathematical induction that $X_n\equiv 1\pmod 3$ is true for all natural numbers n.

I am having difficulty proving that $$X_{n+1}\equiv 1\pmod 3$$

Is true. I figured my solution must include the fact that $$X_{n+1} = X_n + X_{n-1} + X_{n-2} + X_{n-3}$$ therefore $$(X_{n} + X_{n-1} + X_{n-2} + X_{n-3})\equiv 1\pmod 3$$

I know by assumption that $$X_n\equiv 1\pmod 3$$

but I don't know what to do about $X_{n-1}$, $X_{n-2}$ or $X_{n-3}$

I also know that $$X_n = 3Q + 1$$ where Q is a natural number.

I thought this fact would be helpful as well. I am just stuck as to what to do next, any hints on what I should do next would be appreciated. I'd rather just a tip as opposed to someone actually proving so I can try to do it myself. But any help is greatly appreciated.

• Use strong induction. The induction step is to show that if our assertion is true for all $j\lt n$ it is true at $n$. That will be very straightforward in this case. – André Nicolas Oct 8 '15 at 0:39
• Daniel, perhaps you meant $$X_k = X_{k-1} + X_{k-2} + X_{k-3} + X_{k-4}$$ and not $$X_k = X_k -1 + X_k - 2 + X_k - 3 + X_k -4?$$ – Jose Arnaldo Bebita-Dris Oct 8 '15 at 1:39
• yes I did thank you for pointing that out – Daniel Friedland Oct 8 '15 at 2:27