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.

  • $\begingroup$ 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. $\endgroup$ – André Nicolas Oct 8 '15 at 0:39
  • $\begingroup$ 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?$$ $\endgroup$ – Jose Arnaldo Bebita-Dris Oct 8 '15 at 1:39
  • $\begingroup$ yes I did thank you for pointing that out $\endgroup$ – Daniel Friedland Oct 8 '15 at 2:27

Use your initial case be n=4. Then when you assume it is true for all k up to n, you can safely assume it's known at n-3, n -2 and n-1.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.