1

Consider a sequence $g(n)$ defined by $g(1) = 2, g(2) = 3$ and $g(n+1) = 3g(n) - g(n-1)$ for $n > 1$. Prove by induction that $$g(2n) \equiv 3 \pmod{5}\quad \text{and} \quad g(2n+1) \equiv 2 \pmod{5}$$ for $n > 0$.

I'm kind of getting stuck at the induction steps. Please help!

rolandcyp
  • 2,352
Mint
  • 113
  • 3
  • 2
    Welcome to Math Stack Exchange. Please show your work – J. W. Tanner Apr 04 '19 at 22:23
  • So far what I've done in the induction part is to have P(k): g(2n) ≡ 3 (mod 5) and then prove P(k+1): g(2k+2) ≡ 3 (mod 5) by adding g(2k+1) to both sides of P(k) so that g(2k) + g(2k+1) - 3 = 5m + g(2k+1) have its LHS the same as P(k+1) and I don't know what to do next – Mint Apr 04 '19 at 22:30
  • Try $P(k): g(2k)\equiv 3 \pmod 5$ and $g(2k+1)\equiv 2 \pmod5$; what is $3\times2-3 $ and $3\times3-2 \pmod 5$ ? – J. W. Tanner Apr 04 '19 at 22:35

1 Answers1

2

Suppose the thesis holds until $2n$. Then

$$ g(2n+1) = 3g(2n) - g(2n-1) = 3(5k +3) - (5h +2) = 5d +2, $$

and

$$ g(2n+2) = 3g(2n+1) - g(2n) = 3(5k+2) - (5h+3) = 5d +3. $$

Luca Sabatini
  • 562