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

[anemone]

Consider the triangular array of numbers \(\displaystyle 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.

					0
				1		1
			2		2		2
		3		4		4		3
	4		7		8		7		4
5		11		15		15		11		5

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

 

[chisigma]

Consider the triangular array of numbers \(\displaystyle 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.

				1		1
			2		2		2
		3		4		4		3
	4		7		8		7		4
5		11		15		15		11		5

Let \(\displaystyle f(n)\) denote the sum of the numbers in row \(\displaystyle n\). What is the remainder when \(\displaystyle f(100)\) is divided by \(\displaystyle 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:

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

and hence (also using W|A):

\(\displaystyle 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 \(\displaystyle 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$