Programming and a school algebra formula finally deciphered

Explanation is due

I guess you also could have had the same feeling when you learnt algebra at school. Some formulas were clear and understandable, but some were cryptic and it was unclear how would anyone derive them. And then the only way to master it is to memorize it. For example, there is this known formula for a difference of squares:

a2 – b2 = (a – b) * (a + b) = a2 + ab – ba – b2 = a2 – b2 , (1)

Then, there was a little bit more cryptic formula for a difference of cubes, which is not that obvious for a regular student:

a3 – b3 = (a – b) * (a2 + ab + b2) = a3 + a2b + ab2 – ba2 – ab2 – b3 = a3 – b3, (2)

So, I think you get it and the next formula is for a4 – b4 ,

a4 – b4 = (a – b) * (a3 + a2b + b2a + b3) = a4 + a3b + a2b2 + ab3 – ba3 – a2b2 – b3a – b4 = a4 – b4 , (3)

And finally, we get to the most cryptic formula that could be frustrating in a school algebra lesson, the formula for a difference of two positive whole numbers (integers) of power of n

an – bn = (a – b) * (an−1 + an−2b + an-3b2 + … + a2bn-3 + abn−2 + bn−1) , (4)

Now, the last formula seems frightening, and most interestingly one could ask, how did in the world anyone derive it? Also, how do you use it correctly?

Take it slow

Let’s look at it in a slow motion. If we look at how we get from formula (1) to formula (4) we can notice that there is some symmetry in the numbers in the second braces in each of the formula.

So, the second braces in formula (1) have

(a + b)

the second braces in formula (2) have

(a2 + ab + b2)

the second braces in formula (3) have

(a3 + a2b + ab2 + b3)

the second braces in formula (4) have

(an−1 + an−2b + an-3b2 + … + a2bn-3 + abn−2 + bn−1)

Do you see it? When there is a2 on the left side there is a corresponding b2 on the right, when there is a2b on the left, there is a corresponding b2a on the right side, etc. So this is the symmetry I am talking about. The general formula is actually a factorization of a polynomial formula. But we can look at it in a different manner, just to understand how to use it properly. The derivation of the general formula is a little bit more complex and can be found here.

One interesting thing to notice is that the sum of powers of each a, b or there multiplication ab in the second braces is always n – 1.

(a + b) = a1 + b1 , i.e. the powers are 1, 1

(a2 + ab + b2) = a2 + a1b1 + b2 , i.e. the powers are 2, 1 + 1, 2

(a3 + a2b + b2a + b3) = (a3 + a2b1 + a1b2 + b3) , i.e. the powers are 3, 2 + 1, 1 + 2, 3

(an−1+ an−2b + an-3b2 + … + a2bn-3 + abn−2 + bn−1), i.e. the powers are n – 1, n – 2 + 1 = n – 1 , n – 3 + 2 = n – 1, 2 + n – 3 = n – 1, etc.

Now, also let’s pay attention that we can treat 1 as 1 = a0 or 1 = b0, and let’s look again at the expressions above

(a + b) = a1b0 + a0b1 ,

(a2 + ab + b2) = a2b0 + a1b1 + a0b2 ,

(a3 + a2b + b2a + b3) = (a3b0 + a2b1 + a1b2 + a0b3),

(an−1+ an−2b + an-3b2 + … + a2bn-3 + abn−2 + bn−1)

= (an−1b0+ an−2b1 + an-3b2 + … + a2bn-3 + a1bn−2 + a0bn−1),

I hope you can see that there is a systematic pattern which is going on here.

Rules of the game

Rule 1: The number of members in the second braces is always as the power of the initial expression, say two for a2 – b2; three for a3 – b3 etc.

Rule 2: The sum of the powers of each member in the second braces is n – 1, which was already shown in the previous examples.

Pay attention that this can be also proven by mathematical induction. But I leave it as an exercise for you.

How to use this formula and how to zip it

Now that we’ve noticed there is a pattern this pattern show us how to use the formula in a simple way without the need in rote memorization or blindly using someone else derivation.

The only thing is to remember that the first braces always have (a – b) and in the second braces the sum of the powers of each member is n -1. Let’s look at the concrete example of a8 – b8.

Let’s start from the second braces, and write each member without powers in accordance to Rule 1. We know there should be n, i.e. 8 such members.

(ab + ab + ab + ab + ab + ab + ab + ab)

Now, let’s use the Rule 2 and add powers to each member in the second braces, remembering that for a‘s, powers start from n – 1 and decrement by 1 for each consecutive a, and for b‘s powers start from 0 power and increment by 1 for each b until n – 1. Applied to our example,

for a‘s: a7, a6, a5, a4, a3, a2, a1, a0

and b‘s: b0, b1, b2, b3, b4, b5, b6, b7

Now, putting these together in the formula we get,

a8 – b8 = (a – b) * (a7b0 + a6b1 + a5b2 + a4b3 + a3b4 + a2b5 + a1b6 + a0b7)

= (a – b) * (a7 + a6b + a5b2 + a4b3 + a3b4 + a2b5 + ab6 + b7).

Zip it

So, now we ready to zip this formula using the math notation for the sum:

a^n - b^n=(a - b)\sum^{n - 1}_{k = 0} a^{(n - 1) - k}{b^k}

where k increments from 0 to n – 1, i.e. 0, 1 , 2, …, n – 1.

An interesting turn of events

What is nice about this formula is the fact that it’s actually a concise description of an algorithm that checks whether a certain string is a palindrome.

The main idea is to take a sequence of letters (an array of characters in programming speak), and then start comparing

  1. First vs. last letter
  2. Second vs. one before last
  3. etc
  4. For each such case above check whether letters are the same. If there is at least one instance when they are not the same, then it’s not a palindrome.

In Java programming language this algorithm could be implemented as follows (run this code in online Java compiler)

public class Main {
  public static void main (String[]args){
    String word = "TENET";
    System.out.println (isPalindrome(word));
  }
  
  static boolean isPalindrome (String word){
    char[] charArray = word.toCharArray();
    int n = charArray.length;
    
    for (int k = 0; k <= n - 1; k++){
    	if (charArray[k] != charArray[(n - 1) - k]){
    	    return false;
    	}
    }
    return true;
  }
}

Let’s it. Take care.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.