Is there any specific way to solve recurrence of form (example):

\[f(x) = (a \cdot f(x-1) + c) \bmod{r}\] (when recurrence involves modulo).

For recurrence without modular arithmetic I could use generating function method (multiply by \(x^n\), sum, manipulate terms and so on) and often solve it in simple way. Could I somehow exploit information about recurrence solution without modulo to solve recurrence with modulo?

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestWell, we can solve it as \( f(x) = a f(x-1) + c \), and then apply the \( \pmod{r} \) at the end right?

Check out linear recurrence relations to show that \( f(x) = A a^{n-1} + \frac{ c(a^n-1)} { a-1} \).

Log in to reply