Why RAID 1+0 is Better Than RAID 0+1?

In this article, we discuss why RAID 1+0 (stripes of mirrors) is better than RAID 0+1 (mirror of stripes) for those who are building a storage array.

Image credit: Network Storage Server (angle view with case open) from Wikimedia Commons

What is RAID, and why?

RAID (redundant array of independent disks) describes a system of arrangements to combine a bunch of disks into a single storage volume. The arrangements are codified into RAID levels. Here is a summary:

• RAID 0 (striped) essentially concatenates two or more disks. The stripe refers to the fact that blocks from each of the disks are interleaved. If any disk fails, the whole array fails and suffers data loss.
• RAID 1 (mirrored) puts the same data across all disks. It does not increase storage capacity or write performance, but reads can be distributed to each of the disks, thereby increasing read performance. It also allows continued operation until the last disk fails, which improves reliability against data loss (assuming that disk failures happen independently, see discussion below).
• RAID 2, 3, 4, 5 (parity) employ various parity schemes to allow the array to still operate without data loss up to one disk failure.
• RAID 6 (parity) uses two parity disks to allow up to two disk failures without data loss.
• RAID-Z (parity) is a parity scheme implemented by ZFS using dynamic stripe width. RAID-Z1 allows one disk to fail without data loss. RAID-Z2 two disks, and RAID-Z3 three disks.

Disk failures may be correlated by many factors—operational temperature, vibration, wear, age, and manufacture defects shared by the same batch—so they are not fully independent. However, the failures can be somewhat randomized if we mix disks from different vendors or models. Each year, Backblaze publishes hard drive failure rates aggregated by vendor and model (e.g. 2023) which is an invaluable resource to decide which vendor and model to use.

Why use nested RAID?

When disk fails in a RAID up to the tolerated failure without data loss, the failed disk can be replaced with a blank disk, and data is resilvered into the new disk. The resilver time lower bound is determined by the capacity of the disk divided by how fast we can write to it. A larger disk will take longer to resilver. If the disk failures are not fully independent, then there is a greater risk of data loss if another disk fails during resilvering.

By way of example, a 24TB disk at a maximum write speed of 280 MB/s will take about a day to resilver (rule of thumb: each 1 TB takes 1 hour). This makes a large disk somewhat unappealing due to the long resilver time. More realistically, we may want to use smaller disks so they can complete resilvering more quickly.

Creating RAID from smaller capacity bound disks necessitates nesting the RAID arrangements. Here are some ways we can arrange the nesting:

• RAID 0+1 (a mirror of stripes) takes a stripe of disks (RAID 0) and mirror the stripes (RAID 1). When a disk fails, it impacts the entire stripe, and the whole stripe needs to be resilvered.
• RAID 1+0 (a stripe of mirrors) takes a bunch of mirrored disks (RAID 1) and creates a stripe (RAID 0) out of the mirrors. When a disk fails, it impacts just the mirror. When the disk is replaced, only the mirror needs to be resilvered.
• RAID 5+0, RAID 6+0, etc. creates an inner parity RAID combined as an outer stripe (RAID 0).

Nesting are not created equal!

We can see qualitatively from the failure impact point of view that RAID 1+0 has a smaller impact scope, therefore is better than RAID 0+1. But we can also analyze quantitatively what is the probability that a second failed disk might cause total data loss.

• In RAID 0+1, suppose we have N total disks arranged into a 2-way mirror of \( N / 2 \) disk stripes. The first failure already brought down one of the mirrors. The second failed disk would bring down the whole RAID if it happens in the other stripe, or approximately 50% chance. Note that we cannot simply swap striped disks between the mirrors to avert the failure, since disk membership belongs to a specific RAID. You might be able to manually hack around that by hex-editing disk metadata, but that is a risky dealing for the truly desperate person.
• In RAID 1+0, suppose we have N total disks arranged into \( N / 2 \) stripes of 2-way mirrored disks. The first failure already brought down one of the mirrors. The second failed disk would bring down the whole RAID if it happens in the other disk of the same mirror, or approximately \( 1 / N \) chance. The number of failed disks we can tolerate without data loss is a variation to The Birthday Paradox.

Deep dive into aggregate probability of failure

Another way to analyze failure impact quantitatively is to see what happens if we build a RAID 0+1 or RAID 1+0 array using disks of the same average single disk failure rate. We compute the aggregate probability of failure that would suffer data loss, assuming that failures are independent.

• Suppose the probability of average single disk failure is p.
• For RAID 0 with N striped disks, the probability that any of the N disks fails is \( P_0^N(p) = 1 - (1 - p)^N \), i.e. the opposite of all N disks do not fail, a double negation.
• For RAID 1 with N mirrored disks, the probability that all N disks fail at the same time is \( P_1^N(p) = p^N \)
• For RAID 0+1, with k-way mirrors of \( N / k \) stripes, the failure probability is:
  \[
    \begin{aligned}
      P_{0+1}^{k,N/k}(p) & = P_1^{k}(P_0^{N/k}(p)) \\
        & = P_1^k( 1 - (1 - p)^{N/k} ) \\
        & = ( 1 - (1 - p)^{N/k} )^k
    \end{aligned}
  \]
• For RAID 1+0, with \( N / k \) stripes of k-way mirrors, the failure probability is:
  \[
    \begin{aligned}
      P_{1+0}^{N/k,k}(p) & = P_0^{N/k}(P_1^k(p)) \\
        & = P_0^{N/k}(p^k) \\
        & = 1 - (1 - p^k)^{N/k}
    \end{aligned}
  \]

We can plot \( P_{0+1}(p) \) and \( P_{1+0}(p) \) and compare them against p, the probability of single disk failure representing the AFR (annualized failure rate). Here are some examples of p from Backblaze Drive Stats for 2023 picking the models with the largest drive count from each vendor:

MFG	Model	Drive Size	Drive Count	AFR
HGST	HUH721212ALE604	12TB	13,144	0.95%
Seagate	ST16000NM001G	16TB	27,433	0.70%
Toshiba	MG07ACA14TA	14TB	37,913	1.12%
WDC	WUH721816ALE6L4	16TB	21,607	0.30%

In most cases, we are looking at p < 0.01. Some of the models have AFR > 10% but it is hard to tell how accurate the number is due to the small drive count for that model. Those models with a small average age can bias towards high early mortality due to the Bathtub Curve.

We generate the plots in gnuplot using the following commands:

gnuplot> N = 4
gnuplot> k = 2
gnuplot> set title sprintf("N = %g, k = %g", N, k)
gnuplot> plot [0:0.02] x title "p", (1 - (1-x)**(N/k))**k title "RAID 0+1", 1 - (1 - x**k) ** (N/k) title "RAID 1+0"

Number of disks N = 4 with mirror size k = 2 is the smallest possible nested RAID 0+1 or RAID 1+0. At p < 0.01, both RAID 0+1 and RAID 1+0 offer significant improvement over p.

At N = 8 while keeping the same mirror size k=2, we see that both RAID 0+1 and RAID 1+0 still offer improvements over p. However, RAID 1+0 failure rate doubles, and RAID 0+1 more than triples.

At N = 16, the trend of multiplying failure rate continues. Note that RAID 0+1 can now be less reliable than a single disk, while RAID 1+0 still offers 6x improvement over p.

To get the failure rate under control, we need to increase the mirror size to k = 3. Even so, RAID 1+0 failure rate (very close to 0) is still orders of magnitude lower than RAID 0+1.

So from the quantitative point of view, RAID 1+0 is much less probable to suffer a total data loss than RAID 0+1.

Conclusion

As a rule of thumb, when nesting RAID levels, we want the striping to happen at the outermost layer because striping is the arrangement that accumulates failure rates. When we mirror for the inner layer, we reduce the failure rates by orders of magnitude, so the striping accumulates failure rates much slower.

This conclusion also applies to storage pool aware filesystems like ZFS. RAID-Z does not allow adding disks to an existing set. The best practice is to always add disks as mirrored pairs. You can also add a new disk to mirror an existing disk in a pool. Stripes of mirrors offer the most flexibility to expand the storage pool in the future.

This is why RAID 1+0 is better.

Infinite Monkey Theorem, Debunked

If you let a monkey hit random keys on a typewriter for an infinite amount of time, will it happen to write the complete works of Shakespeare? Common wisdom says that not only will it write Shakespeare, but it will “almost surely” type every possible text an infinite number of times.

The proof idea goes like this: the probability to produce a permutation matching the complete works of Shakespeare is very small, but still greater than zero, so it will “almost surely” happen.

This is assuming that the monkey will eventually produce such permutation with a non-zero probability.

What if some permutations are simply not possible? There could be several reasons why this particular monkey and this particular typewriter could not have written Shakespeare. In order of increasing complexity:

• Some letters on the keyboard are broken, so some letters in the works of Shakespeare could not be typed.
• Due to the clumsiness of the monkey, it is only able to hit the space bar before or after hitting the letters above it. This means that every word has to always begin and end with ‘z’, ‘x’, ‘c’, ‘v’, ‘b’ ‘n’, or ‘m’. Shakespeare often used words that do not satisfy this criteria, so the works of Shakespeare could not have been written.
• The monkey is not able to repeat what it types within a certain number of words, so phrases like “to be or not to be” can never be written.

Infinity does not mean that it will allow every permutation. An example is the infinite sequence that concatenates the set of numbers consisting of only even digits: 0 2 4 6 8 20 22 24 26 28 40 42 44 46 48 etc. This sequence is infinite, but it would never contain the number ‘1’.

(On the other hand, the sequence of all even numbers concatenated will contain all finite numbers, including the odd numbers; since starting from 10—which is still an even number—we simply ignore the last digit and look at the tens and above, e.g. 123 is contained in 1230 1232 1234...)

This is not an argument about “almost surely” being practically zero. Instead, we are simply saying that infinite monkey is not almost surely, as the output is handicapped in some way albeit still infinite.

If we want to apply the infinite monkey theorem elsewhere, infinity alone is not sufficient. We have to also show that the desired permutation has a non-zero probability to happen, as this is not a given. On the contrary, an application that only establishes infinity can be disproven by showing that the desired output actually has a zero probability of happening.

∞ ⨉ 𝜀 = ∞ but ∞ ⨉ 0 = 0

In reality, we often confuse the mechanism of the permutation with the existence of output. We cannot say that the complete works of Shakespeare exists in the output implies that it must have been produced by the monkey. What if we have a programmed typewriter such that, if the monkey hits ‘s’ a million times in a row, would insert the complete works of Shakespeare? The complete works “exists” in the output, but it is not produced through the monkey's mechanism of permutation.

(This is analogous to the panspermia hypothesis saying that life could have been introduced from an external source rather than permuted naturally within the system. The hypothesis allows that a system capable of sustaining finite life may not have been able to produce life infinitely.)

Showing that some improbable event has zero probability of being produced could be quite difficult but “almost surely” doable. However, if we try to categorically argue that “almost surely” is practically zero, then the argument is only “almost surely” believable.

“Hybrid Log Float” 14-bit to 10-bit Pixel Transfer Function

Here I propose a Hybrid Log Float as a transfer function that maps from a 14-bit linear pixel to 10-bit non-linear pixel in a way that is inspired by floating point numbers. Unlike 16-bit half float, we don't have enough bits for both an exponent and the mantissa. We also don't need to represent fractions or negative numbers. Having a custom integer bit format allows us to store more significant figures while preserving the widest dynamic range from the input. Expressing the transfer function as an integer bit format allows the encoding and decoding between linear and non-linear colorspaces to be fast and bit-accurate without using a lookup table.

First, some background information. In this past year, I've had the pleasure of shooting some videos (here, here, and here) with Panasonic GH5s, which is a fine camera. When it was introduced in January, it was the first compact interchangeable lens camera that could internally record DCI 4K in 4:2:2 10-bit H.264. Such recording ability was only later superseded by the Blackmagic Design Pocket Cinema Camera 4K (BMPCC) released in September, which records in 12-bit CinemaDNG RAW or 4:2:2 10-bit ProRes. These two cameras have a very similar sensor (if not the same) that outputs 14-bit per pixel. GH5s will generate 14-bit RW2 when taking pictures (e.g. time lapse), but not the BMPCC.

The sensor's 14-bit per pixel output means that the maximum theoretical dynamic range is 14 stops. That's because each stop is twice or half the amount of light, so the number of bits per sample corresponds to the number of stops. This is corroborated by the assessment on GH5s done by Alan Roberts in EBU Tech 3335 S29. He measured 14.6 stops for Hybrid Log Gamma and 13.5 for V-Log L. Both Hybrid Log Gamma and V-Log L are different picture profiles that map the 14-bit sensor output to the 10-bit codec. The measured dynamic range exceeds the theoretical somewhat, but it's within measurement error. Also, quantum uncertainty means that light level below the sensor's sensitivity could sometimes be picked up as temporal noise. But as a rule of thumb, we can think of the number of bits as the number of stops.

It is interesting how dynamic range can be affected the way the codec downsamples 14-bit sensor output to 10-bit. The most naive approach is to simply truncate the least significant 4 bits, but that means you lose 16 shades in the shadow and end up with only 10 stops of dynamic range. This is pretty harsh if someone wants to recover shadow from an underexposed picture. This is probably what Like709 picture profile does on GH5s (simulates BT.709 color space) since it only measures 10.3 stops.

The Hybrid Log Gamma (HLG) and V-Log L picture profiles take advantage of the way human eyes perceive intensities of light non-linearly, so they downsample 14-bit sensor output (which is the linear measurement of light) to 10-bit for codec using transfer functions that preserve the most perceptible shades. However, the picture profiles are designed for different purposes. HLG is calibrated for consumer TVs that render HDR in BT.2100 colorspace, which is hard to color grade (changing the look and feel of a picture by manipulating colors) because the colorspace is non-linear. V-Log L has a flatter picture profile which makes color grading easier, but it's still better to convert it to a linear colorspace for more accurate color grading. Non-linear colorspace can be converted back to linear using a look up table (LUT).

Then two things had occurred to me.

First, cameras should really provide a 16-bit codec. If the sensor data are only 14-bits, normalize the sample by zero-padding the least significant bits. The additional bits aren't a significant storage overhead (probably negligible after either lossless or lossy compression), and it makes processing on a computer a lot more efficient since the samples are naturally aligned to 16-bit short integers, which is well suited for SIMD instructions. Unfortunately, the only 16-bit capable codec today is HEVC, and it's not widely implemented. Both ProRes RAWand CineForm are currently 12-bit, even though their coding principles (DCT for ProRes, Wavelet for CineForm) are bit-agnostic, so it's just a matter of someone implementing it. I suspect that 16-bit codec will be much easier to implement. It would avoid this bit shifting voodoo to unpack 14-bit integers.

Second, since a 16-bit capable codec is a bit out of reach, it's beneficial to have a transfer function that is bit-accurate (to minimize rounding errors) but still takes into account the way human perceives light intensities: we tend to notice minute light variances in darkness, but we are less sensitive to small variances when the environment is bright.

The result is the Hybrid Log Float transfer function, which encodes a linear value to logarithmic scale and decodes back to the same linear colorspace with predictable allocation of significant figures. The idea is to encode the exponent as the number of leading one bits in unary, and the rest of the bits can be used for storing significant figures, in a way that's inspired by the UTF-8 encoding. On the other hand, the A-Law, µ-Law companding algorithms count the exponent in binary in the same way Minifloat works (but different number of bits allocated to exponent and mantissa), rather than in unary.

To illustrate how unary exponent works, let's consider 14-bit to 12-bit reduction first.

It's broken down into four spans. The first span (a) has 11 bits of significant figures, and is encoded verbatim as linear. The second span (b) has 10 bits. The last two spans (c) and (d) each have 9 bits, and is actually ½ log(x) = log(√x).

Here is the 14-bit to 10-bit reduction using the same approach.

The spans are (a) 9-bit linear, (b) 8-bit log, (c) 7-bit 1/2 log, (d) 6-bit 1/4 log, (e) 5-bit 1/8 log, (f) 5-bit 1/8 log. Notice that the two highlight tiers only have 5-bits, or 32 shades, which may not be enough to recover highlights. Since this encoding allocates more bits for the shadows, it prefers the picture to be slightly under-exposed.

Here is an alternative 14-bit to 10-bit encoding that reserves more bits for the midtones and highlights, so it has better color accuracy for highlight recovery. The trick is to pre-allocate bits for counting the exponent in binary rather than unary at first, but revert back to unary exponent afterwards.

The difference is that spans (b), (c), and (d) are now 7-bits each, or 128 shades, at 1/2 log scale, using three bits to count the exponent. The upper two tiers (e) and (f) have 6-bits each, or 64 shades, at 1/4 log(x) scale.

Here is a plot comparing:

• Two variants of Hybrid Log Float (float v1, float v2)
• Log curve normalized to the output range (73*log2(x))
• Gamma correction curve at γ = 2.4 normalized to the input range (x ** (1/2.4) * 18) and the output range (x ** (1/2.4) * 57).
• Linear normalized to the input range (x / 16) and the output range (x).

In the plot, the x axis is the input range, and the y axis is the output. A steeper slope indicates better color resolution. Clipping happens when the curve goes off the chart.

It may seem that log provides too much value resolution for shadow, and gamma 2.4 seems to provide just the right amount. But if we zoom into the input range 0-256, we can see that both log and gamma use much wider output range than the input range, resulting in wasted bits and more difficult noise reduction since the noise is amplified. Both Hybrid Log Float variants follow the same slope as linear x (normalized to output) at this scale, so we don't have the noise amplification problem.

Overall, Hybrid Log Float has the following benefits:

• It does not waste output bits in the deep shadow, so it doesn't have the noise amplification problem that log or gamma may suffer.
• Good midtone resolution.
• It resolves highlights similarly like log for greater dynamic range.
• The alternative second variant of Hybrid Log Float provides better midtone and highlight resolution than the first variant.

Also most importantly, Hybrid Log Float provides bit-accurate and efficient decoding back to the linear colorspace, so the color grading can be done the most accurately.

Last but not the least, while I would like to see cameras record to Hybrid Log Float when using a legacy 10-bit codec, ultimately I would like to see native 16-bit codecs so the post-processing does not have to waste precious machine cycles realigning the awkward 10-bit integers.

Fermat Numbers and Bit Mask

There is a little known application of Fermat numbers for generating bit masks, that I discovered back in 2010 while implementing "counting the number of one bits" using C++ template meta-programming. In the algorithm, bit masks such as 0x55555555, 0x33333333, 0x0f0f0f0f, etc. are used to mask out bits in specific locations. These bit masks can be generated by dividing the maximum integer 0xffffffff (or simply ~0u) against Fermat numbers 3, 5, 17, 257, 65537, etc.

Hex	Binary	Expression
0x5555...	0101010101010101...	~0u / 3
0x3333...	0011001100110011...	~0u / 5
0x0f0f...	0000111100001111...	~0u / 17
0x00ff...	0000000011111111...	~0u / 257
and so on...

It's not a coincidence that integers with all one bits set can be divided cleanly by a Fermat number, and this works with 8-bit, 16-bit, 32-bit, 64-bit, and beyond. To understand why, a \(k\)-bit all-one integer is \(2^k - 1\). In particular, \(k = 2^n\) in our case. We can factor \(2^{2^n} - 1\) using the formula \(a^2 - b^2 = (a + b)(a - b)\) we learned in grade school, here using the special case \(b = 1\), so \(a^2 - 1 = (a + 1)(a - 1)\).
\begin{align}
2^{2^n} - 1 & = (2^{2^{n - 1}} + 1)(2^{2^{n - 1}} - 1) \\
 & = (2^{2^{n - 1}} + 1)(2^{2^{n - 2}} + 1)(2^{2^{n - 2}} - 1) \\
 & = (2^{2^{n - 1}} + 1)(2^{2^{n - 2}} + 1)(2^{2^{n - 3}} + 1)(2^{2^{n - 3}} - 1) \\
 & = \dots
\end{align}
Conveniently, the last term \(2^{2^0} - 1\) is just \(1\), so we can write the product in terms of \(F_i = 2^{2^i} + 1\) for the \(i\)-th Fermat number,
\[ 2^{2^n} - 1 = \prod_{i=0\dots n-1}{2^{2^i} + 1} = \prod_{i=0\dots n-1}{F_i} \]
For example,

\(k\)	\(2^k - 1\)	Expression
2	3	\(3 \)
4	15	\(3 \times 5 \)
8	255	\(3 \times 5 \times 17 \)
16	65535	\(3 \times 5 \times 17 \times 257\)
32	4294967295	\(3 \times 5 \times 17 \times 257 \times 65537\)
and so on...

So how are Fermat numbers related to bit mask construction? It turns out that if you write 3, 5, 17, 257, 65537 in binary, you get 11, 101, 1 0001, 1 0000 0001, and 1 0000 0000 0000 0000 0000 0000 0000 0001 respectively. If you multiply 101 (5) and 1 0001 (17), you get alternating patterns of 0101 0101 (85). If you multiply this by 11 (3), you get an 8-bit all-one integer 1111 1111 (255). Conversely, you can take a pattern "out of circulation" by dividing the all-one integer by a Fermat number which is one of its factors.

Appendix: Counting the number of one bits using C++ template meta-programming

We start with the straightforward bit vector algorithm:

x = ((x >> 1) & 0x55555555) + (x & 0x55555555);
x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
// etc.

which can be represented by the following for-loop:

for (int n = 1; n < sizeof(Tp) * 8; n *= 2)
  Tp mask = ~0 / ((1 << n) + 1));
  x = ((x >> n) & mask) + (x & mask);
}

In the template meta-programming version, the template __unroll_shift_mask_add essentially unrolls into the for-loop above, but in a manner that is agnostic to the actual integer type.

template<unsigned int n, typename Tp>
struct __unroll_shift_mask_add {
  static Tp compute(Tp x) {
    Tp y = __unroll_shift_mask_add<n / 2, Tp>::compute(x);
    Tp mask = ~Tp(0) / ((Tp(1) << n) + 1);
    return ((y >> n) & mask) + (y & mask);
  }
};

template<typename Tp>
struct __unroll_shift_mask_add<0u, Tp> {
  static Tp compute(Tp x) { return x; }
};

template<typename Tp>
Tp one_bits(Tp x) {
  return __unroll_shift_mask_add<sizeof(Tp) * 8 / 2, Tp>::compute(x);
}

Proof of Sum of Exponential Powers

My renewed interest in proof of exponent laws came from reading the Harvard Entrance Exam, 1869, which David Robert Palmer painstakingly typed up. In the exam there were sections of Latin and Greek, History and Geography, are various mathematics. It's fascinating that the words in Latin and Greek are already provided, so knowing how to conjugate is all that is required. The maths section are heavily calculation based. It seems that these sections serve to test only how nimble the minds are in solving known problems, but not so much whether the students exhibit the thought process of solving unknown problems. But one question intrigued me.

Question (3) in the algebra section reads, "What is the reason that when different powers of the same quantity are multiplied together their exponents are added?" It is asking about the exponent law for product of powers, \( a^x a^y = a^{x+y} \). Knowing the prestige of Harvard, giving an informal answer is likely not satisfactory. But most of the so called "proofs" that are prevalent in textbooks essentially boil down to the following reasoning.
\[ \underbrace{a a \dots a }_{x \text{ times}} \cdot \underbrace{a a \dots a}_{y \text{ times}} = \underbrace{a a a a \dots a a }_{x + y \text{ times}} \]
This appeals to the intuitive understanding that \( a^x \) is \(a\) multiplied \(x\) times, so when you multiply the result also by \(a\) for another \(y\) times, you get \( a^{x+y} \). This is hardly satisfying as a proof.

Another "proof" is to reduce this to the additive law of logarithms \( \log{xy} = \log{x} + \log{y} \), but this is like throwing the hot potato to someone else.
\[ \log{a^x a^y} = \log{a^x} + \log{a^y} = x + y \\
a^{\log{a^x a^y}} = a^{x+y} \]
And since \( a^{\log{c}} = c \) i.e. log is the inverse of exponent, so \( a^{\log{a^x a^y}} = a^x a^y = a^{x+y} \).

There are other exponent laws without formal proofs, but for this article I'm going to focus on the sum of powers.

Formal proof

We appeal to proof by induction for the formal proof. First we establish the base case for exponentiation:
\[ a^0 = 1 \]
Also recall that \(1\) is the multiplicative identity, so \( x\cdot 1 = 1\cdot x = x \), and \(0\) is the additive identity, so \( x+0 = 0+x = x \). From this, we can prove the base case where \( y = 0 \), i.e. \( a^x a^0 = a^x \cdot 1 = a^x = a^{x+0} \).

Now for the inductive case, we need both the axiom of exponentiation \( a^x \cdot a = a^{x+1} \) and the induction hypothesis \( a^x a^y = a^{x+y} \). We proceed to show that \( a^x a^{y+1} = a^{x+y+1} \).
\[ a^x (a^{y+1}) \underbrace{=}_{\text{axi.}} a^x (a^y a^1) \underbrace{=}_{\text{assoc.}} (a^x a^y) a^1 \underbrace{=}_{\text{I.H.}} a^{x+y} a^1 \underbrace{=}_{\text{axi.}} a^{(x+y)+1} \]
In the equations above, "axi." means the axiom of exponentiation, "I.H." means application of induction hypothesis, and "assoc." means associativity (which is true of all multiplicative groups, e.g. matrix multiplication).

Having painstakingly established a formal proof of the product of powers, there is a notable limitation, namely that we only allow natural number exponents, \( \{x, y\} \subseteq \mathbb{N} \). In particular, we don't allow negative (e.g. -3) or fractions (e.g. 3.14159...). Indeed, the real number domain has declarative properties that evade the mere application of modus ponens in discrete logic, which gives rise to the famous satire Alice in Wonderland.

Proof sketch in real number domain

Fortunately, all is not lost in the real number domain. We can invoke Taylor's theorem to expand the infinite series for calculating \( e^x \) and \( e^y \), multiply the two series, and see if \( e^{x+y} \) expands to the result of the multiplication.

The Taylor series for \( e^x \) is:
\begin{array}{rcl}
e^x & = & \sum^{\infty}_{n=0} {x^n \over n!} \\
 & = & 1 + {x^1 \over 1!} + {x^2 \over 2!} + {x^3 \over 3!} + {x^4 \over 4!} + \dots \\
 & = & 1 + x + {x^2 \over 2} + {x^3 \over 6} + {x^4 \over 24} + \dots
\end{array}
The following table multiplies the Taylor series for \( e^x \) and \( e^y \).
\begin{array}{c|cc}
\times & 1 & x & x^2 \over 2 & x^3 \over 6 & x^4 \over 24 & \dots \\ \hline
1 & 1 & x & x^2 \over 2 & x^3 \over 6 & x^4 \over 24 & \dots \\
y & y & xy & x^2 y \over 2 & x^3 y \over 6 & x^4 y \over 24 & \dots \\
y^2 \over 2 & y^2 \over 2 & xy^2 \over 2 & x^2 y^2 \over 4 & x^3 y^2 \over 12 & x^4 y^2 \over 48 & \dots \\
y^3 \over 6 & y^3 \over 6 & xy^3 \over 6 & x^2 y^3 \over 12 & x^3 y^3 \over 36 & x^4 y^3 \over 144 & \dots \\
y^4 \over 24 & y^4 \over 24 & xy^4 \over 24 & x^2 y^4 \over 48 & x^3 y^4 \over 144 & x^4 y^4 \over 576 & \dots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\end{array}
The Taylor series for \( e^{x + y} \), expanded individually, is:
\begin{array}{c}
1 &+& (x+y) &+& {(x+y)^2 \over 2} &+& {(x+y)^3 \over 6} &+& {(x+y)^4 \over 24} &+& \dots \\
 & & || & & || & & || & & || \\
 & & x & & x^2 \over 2 & & x^3 \over 6 & & x^4 \over 24 \\
 & & y & & xy & & x^2 y \over 2 & & x^3 y \over 6 \\
 & & & & y^2 \over 2 & & xy^2 \over 2 & & x^2 y^2 \over 4 \\
 & & & & & & y^3 \over 6 & & xy^3 \over 6 \\
 & & & & & & & & y^4 \over 24
\end{array}
As you can see, the expansion of each term corresponds diagonally to the multiplication table above, so we can indeed show by Taylor expansion that \( e^x e^y = e^{x+y} \). This is only a proof sketch, but the enterprising mind could organize the table into a formal proof, using Binomial Theorem and Cauchy Product.

You might have noticed that we have only established the product law at base \(e\) but not other bases. For the other bases, recall that \( a^x = e^{x \ln a} \), so we have:
\[ a^x a^y = e^{x \ln a} e^{y \ln a} = e^{(x \ln a) + (y \ln a)} = e^{(x+y)\ln a} = a^{x+y} \]

Conclusion

There are two reasons why I suspect the Harvard entrance exam only expected the informal reasoning of counting the number of multiplicands. Cauchy (1789-1857) product is a fairly recent development to the time of the exam in 1869, which makes it unlikely to become part of the curriculum. There were no other questions that require the use of proof by induction so that it is also unlikely to be part of the curriculum either.

On the other hand, it is only after I became older (and overeducated) that I realize a lot of maths I was taught in grade school were really just informal proof sketches, and even so I didn't learn to question the profoundness of their limitations. The informal proof sketch of counting the multiplicands is limited to exponent in the natural number domain and would not work for real number exponents. I spent the better parts of my youth learning faux math!

Laws in the real number domain cannot be proven by counting alone because real numbers are uncountable. For this case I appealed to Taylor's Theorem, first expanding the polynomial series and showing the combined series are equal. I suspect many of the real number laws could use the same treatment.