Associated Topics || Dr. Math Home || Search Dr. Math

### Math Virus Formula

```
Date: 10/23/2001 at 05:49:48
From: Victor Lee
Subject: I cannot figure out the formula to a math virus

Hello Dr. Math,

I have to figure out a formula for a math virus. The virus spreads to
all the squares directly touching each other (not including
diagonally), and I have found the formula for the number of newly
infected cells (although this does not include the first minute.) The
formula is 4n + 4, but I also have to find the formula for the total
number of infected cells, and despite trying many times to figure it
out, I still have no clue.

infected cells goes up by 4 cells each minute, i.e. 3 minutes is 13
and 4 minutes is 25.

I will be extremely appreciative if you help me with this.
Thanks,
Victor Lee
```

```
Date: 10/23/2001 at 14:41:02
From: Doctor Greenie
Subject: Re: I cannot figure out the formula to a math virus

Hi, Victor -

This is a nice problem. There are many opportunities with this problem
to be "clever" to make finding the answer quite easy. I will present
the solution in exactly the way I found it, so that you can see how
the effort required to reach a solution can be reduced by studying the
problem to find the "easy" path.

Let's start by drawing some pictures and making a table of our
results....

+---+      n=0
|   |      new squares: 1
+---+      total squares: 1

+---+
|   |
+---+---+---+      n=1
|   |   |   |      new squares: 4
+---+---+---+      total squares: 5
|   |
+---+

+---+
|   |
+---+---+---+
|   |   |   |
+---+---+---+---+---+      n=2
|   |   |   |   |   |      new squares: 8
+---+---+---+---+---+      total squares: 13
|   |   |   |
+---+---+---+
|   |
+---+

+---+
|   |
+---+---+---+
|   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+---+---+      n=3
|   |   |   |   |   |   |   |      new squares: 12
+---+---+---+---+---+---+---+      total squares: 25
|   |   |   |   |   |
+---+---+---+---+---+
|   |   |   |
+---+---+---+
|   |
+---+

So we have

figure number   additional squares   total squares
--------------- -------------------- ---------------
0                 1                  1
1                 4                  5
2                 8                 13
3                12                 25
...

The sequence we get for the numbers of squares for n = 1, 2, 3, ... is

5, 13, 25, ...

One way to find a formula for generating a sequence like this is the
method of finite differences. Here is a link to a page in the Dr. Math
archives where there is a lengthy discussion of this method:

Method of Finite Differences
http://mathforum.org/dr.math/problems/gillett.10.12.00.html

While the method of finite differences is often very useful, I
suspected I could find the answer more quickly by analyzing the
figures and coming up with some shortcut for finding the total number
of squares in the n-th figure.

My approach (taken with too little forethought, as you will see later)
was to break up the figure for the case n=3 as follows:

+---+   +---+   +---+
|   |   |   |   |   |
+---+---+   +---+   +---+---+
|   |   |   |   |   |   |   |
+---+---+   +---+   +---+---+
|   |
+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
|   |
+---+---+   +---+   +---+---+
|   |   |   |   |   |   |   |
+---+---+   +---+   +---+---+
|   |   |   |   |   |
+---+   +---+   +---+

The number of squares in this figure is the number in the central
"cross" figure plus the number in the four identical "stair-step"
figures. The number in the central cross figure for the n-th case is
(4n+1); the number in each of the four stair-step figures is the sum
of the integers from 1 to (n-1), which I know to be n(n-1)/2.  So the
total number of squares in the n-th figure is

(4n+1) + 4(n(n-1)/2))
= 4n + 1 + 2(n^2 - n)
= 4n + 1 + 2n^2 - 2n
= 2n^2 + 2n + 1

When I got to this point, I tried to find a simpler way to write this
formula; after staring at it for a moment, I realized that

2n^2 + 2n + 1
= (n^2) + (n^2 + 2n + 1)
= n^2 + (n+1)^2

In words, this formula is quite simple - the number of squares in the
nth figure is the sum of the squares of n and (n+1).

Checking this formula out quickly for n = 1, 2, and 3, we find

n=1: n^2 + (n+1)^2 = 1+4 = 5
n=2: n^2 + (n+1)^2 = 4+9 = 13
n=3: n^2 + (n+1)^2 = 9+16 = 25

So the formula appears to be correct, indicating I did not make any
mistakes with my reasoning or with my algebra.

But after I came up with this formula, I went back to look at my
figures to see if I could come up with this same formula more quickly
than the way I did. And just a bit of looking at the figure showed me
what would have been a much quicker path to the formula.

The quicker path I found was to break up the n-th figure in a
different manner than I did originally. This time, I break up the n-th
figure as follows:

+---+
|   |
+---+---+---+
|   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   |   |   |
+---+---+---+
|   |
+---+

Now the figure is comprised of two parts. The number of squares in the
first part is the sum of the first n odd integers, which I know to be
n^2; and the number of squares in the second part is the sum of the
first (n+1) odd integers, which I know to be (n+1)^2. So by breaking
up the figure in this manner I am led immediately to the formula

number of squares in n-th figure = n^2 + (n+1)^2

Thanks for the interesting problem. I got some valuable problem-
solving experience playing with it.

I hope all this helps. Write back if you have any further questions on
this.

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Basic Algebra
High School Number Theory
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search