MHB Find the remainder when f(100) is divided by by 100

[anemone]

Consider the triangular array of numbers $$0,\;1,\;2,\;3,\cdots$$ along the sides and interior numbers obtained by adding the two adjacent numbers in the previoius row. Row 1 through row 6 are shown as below.

[TABLE="width: 500"]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]0[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]1[/TD]
[TD][/TD]
[TD]1[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]2[/TD]
[TD][/TD]
[TD]2[/TD]
[TD][/TD]
[TD]2[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD]3[/TD]
[TD][/TD]
[TD]4[/TD]
[TD][/TD]
[TD]4[/TD]
[TD][/TD]
[TD]3[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD]4[/TD]
[TD][/TD]
[TD]7[/TD]
[TD][/TD]
[TD]8[/TD]
[TD][/TD]
[TD]7[/TD]
[TD][/TD]
[TD]4[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]5[/TD]
[TD][/TD]
[TD]11[/TD]
[TD][/TD]
[TD]15[/TD]
[TD][/TD]
[TD]15[/TD]
[TD][/TD]
[TD]11[/TD]
[TD][/TD]
[TD]5[/TD]
[/TR]
[/TABLE]

Let $$f(n)$$ denote the sum of the numbers in row $$n$$. What is the remainder when $$f(100)$$ is divided by $$100$$?

 

[chisigma]

Consider the triangular array of numbers $$0,\;1,\;2,\;3,\cdots$$ along the sides and interior numbers obtained by adding the two adjacent numbers in the previoius row. Row 1 through row 6 are shown as below.

[TABLE="width: 500"]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]1
[/TD]
[TD][/TD]
[TD]1
[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]2
[/TD]
[TD][/TD]
[TD]2
[/TD]
[TD][/TD]
[TD]2
[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD]3
[/TD]
[TD][/TD]
[TD]4
[/TD]
[TD][/TD]
[TD]4
[/TD]
[TD][/TD]
[TD]3
[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD]4
[/TD]
[TD][/TD]
[TD]7
[/TD]
[TD][/TD]
[TD]8
[/TD]
[TD][/TD]
[TD]7
[/TD]
[TD][/TD]
[TD]4
[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]5
[/TD]
[TD][/TD]
[TD]11
[/TD]
[TD][/TD]
[TD]15
[/TD]
[TD][/TD]
[TD]15
[/TD]
[TD][/TD]
[TD]11
[/TD]
[TD][/TD]
[TD]5
[/TD]
[/TR]
[/TABLE]

Let $$f(n)$$ denote the sum of the numbers in row $$n$$. What is the remainder when $$f(100)$$ is divided by $$100$$?

The sequence $f_{n}$ is solution of the difference equation... $$f_{n+1} = f_{n} + 2^{n+1},\ f_{0}=0\ (1)$$

... and the solution of (1) is... $$f_{n} = \sum_{k=1}^{n} 2^{k} = 2\ (2^{n}-1)\ (2)$$

From (2) using 'Monster Wolfram' we derive...

$$2\ (2^{100}-1)\ \text{mod}\ 100 = 50\ (3)$$ ... but probably a more clever way to arrive to (3) exists... Kind regards $\chi$ $\sigma$

 

[MarkFL]

I found by observation that:

$$f(n)=2\left(2^{n-1}-1 \right)$$

and hence (also using W|A):

$$74\equiv f(n)\,\,\,\,(\text{mod }100)$$

 

[Nono713]

By observation I got $f(n) = 2^n - 2$, hence $f(100) = 2^{100} - 2$.

Now $2^5 \equiv 32 \pmod{100}$, so $2^{10} \equiv 32^2 \equiv 24 \pmod{100}$, then $2^{50} \equiv 24^5 \equiv 24 \pmod{100}$ and we conclude that $2^{100} \equiv 24^2 \equiv 76 \pmod{100}$.

Therefore $f(100) \equiv 76 - 2 \equiv 74 \pmod{100}$.

 

[chisigma]

Of course it is a trivial problem of indexes but it is...

$$f_{0} = 2\ (2^{0}-1) = 0$$

$$f_{1} = 2\ (2^{1}-1) = 2$$

$$f_{2} = 2\ (2^{2}-1) = 6$$

$$f_{3} = 2\ (2^{3}-1) = 14$$

... so that in general is...

$$f_{n} = 2\ (2^{n}-1)$$

Kind regards$\chi$ $\sigma$

 

[anemone]

Of course it is a trivial problem of indexes but it is...

$$f_{0} = 2\ (2^{0}-1) = 0$$

$$f_{1} = 2\ (2^{1}-1) = 2$$

$$f_{2} = 2\ (2^{2}-1) = 6$$

$$f_{3} = 2\ (2^{3}-1) = 14$$

... so that in general is...

$$f_{n} = 2\ (2^{n}-1)$$

Kind regards$\chi$ $\sigma$

Hi chisigma,

According to the general formula that you derived in the above manner, I believe f(100) is obtained when $$n=99$$.

 

[I like Serena]

By observation I got $f(n) = 2^n - 2$, hence $f(100) = 2^{100} - 2$.

Now $2^5 \equiv 32 \pmod{100}$, so $2^{10} \equiv 32^2 \equiv 24 \pmod{100}$, then $2^{50} \equiv 24^5 \equiv 24 \pmod{100}$ and we conclude that $2^{100} \equiv 24^2 \equiv 76 \pmod{100}$.

Therefore $f(100) \equiv 76 - 2 \equiv 74 \pmod{100}$.

Since I like the Chinese Remainder Theorem (CRT). (Inlove)CRT says that the map $\psi: \mathbb Z/100\mathbb Z \to \mathbb Z/4\mathbb Z \times \mathbb Z/25\mathbb Z$ given by $\psi: x \text{ mod }{100} \mapsto (x \text{ mod }4, x \text{ mod }{25})$ is an isomorphism.

Since $\phi(25)=20$, we know from Euler's Theorem that $2^{20} \equiv 1 \pmod{25}$.
So $\psi(2^{100} - 2) \equiv (2^{100} - 2 \text{ mod }{4}, 2^{100} - 2 \text{ mod }{25}) \equiv (- 2 \text{ mod }{4}, 1^5 - 2 \text{ mod }{25}) \equiv (-2 \text{ mod }{4}, -1 \text{ mod }{25})$.

From the second argument, it follows that $2^{100} - 2$ is equivalent to one of $24, 49, 74, 99 \pmod{100}$.
Only $74$ fits with the first argument.

So $f(100) \equiv 2^{100} - 2 \equiv 74\pmod{100}. \qquad \blacksquare$