4

I'm an undergraduate math major and sometimes I find proofs that seem to use algebraic 'tricks' to reach their conclusions. The 'trick' that I see most often is a change of variable or the use of an obscure identity, and intuitively I have no idea how someone would realize that this is a viable option.

Is there a field of study that concerns itself with 'trick' algebraic operations, or maybe a field of study that explains how to determine if/when a change of variable/identity substitution might be an appropriate technique given a situation?

For a specific example, I'll reference the proof of the equation for the expectation of the power of a Bernoulli random variable. I can't imagine how someone would discover this proof.

We will now examine the properties of a binomial random variable with parameters $n$ and $p$. To begin, let us compute its expected value and variance. Now,

$$\begin{align} E[X^k] &= \sum_{i = 0}^ni^k\binom{n}{i}p^i(1 - p)^{n - i}\\ &= \sum_{i = 1}^ni^k\binom{n}{i}p^i(1 - p)^{n - i} \end{align}$$

Using the identity, $$i\binom{n}{i} = n\binom{n - 1}{i - 1}$$ gives

$$\begin{align} E[X^k] &= np\sum_{i = 1}^ni^{k - 1}\binom{n - 1}{i - 1}p^{i - 1}(1 - p)^{n - i}\\ &= np\sum_{j = 1}^{n - 1}(j + 1)^{k - 1}\binom{n - 1}{j}p^j(1 - p)^{n - 1 - j} && \overset{\text{by letting}}{j = i - 1}\\ &= npE[(Y + 1)^{k - 1}] \end{align}$$

Lê Thành Đạt
  • 4,228
Battlefrisk
  • 69
  • maybe lookup, "combinatorial identities" for this particular case? – rubikscube09 Mar 18 '20 at 23:49
  • Do you want [tag:algebra-precalculus] rather than [tag:linear-algebra]? – J. W. Tanner Mar 18 '20 at 23:50
  • I'm hoping to get an answer that is broader than this particularcase. @Tanner i will modify, it should probably be algebra-precalc – Battlefrisk Mar 18 '20 at 23:53
  • When obsessed people scour an area, they will find whatever there is to be found, no matter how subtle. Just look at Summoning Salt's YouTube videos about the history of video game speed running. The tricks they have stumbled over are incredibly subtle. By the way, there is a much more intuitive way to understand the expected value of a binomial remain variable $X$. Write $X$ as a sum of independent Bernoulli RVs with parameter $p$, so $X = \sum_{i=1}^n X_i$, then take the expected value of both sides and use the fact that $E(X_i) = p(1-p)$. – littleO Mar 18 '20 at 23:59
  • This is probably not very helpful, but I think we find these things by thinking about familiar patterns and forms learnt by reading and questioning example proofs: for example, the second line in your quoted proof changes the lower bound of a sum from $0$ to $1$, which looks suspicious, but presumably works because your are given that $i\neq 0$, so that $i^0 = 0$. In your quoted example, I don't see enough overall context about what the proof was trying to achieve to say any more. – Rob Arthan Mar 19 '20 at 00:01
  • @littleO, so you're saying that the answer to how to figure these things out myself is to leave no stone unturned. That there isn't an underlying pattern for these sorts of tricks other than experience, instinct, and trying any trick I can think of. – Battlefrisk Mar 19 '20 at 00:04
  • @Rob it is precisely this 'familiar patterns and forms' that I want to study, by abstracting away from the examples in my other classes where they seem to constantly pop up. – Battlefrisk Mar 19 '20 at 00:07
  • 1
    What is the symbol in the second equality (?) and what does it mean? – Jair Taylor Mar 19 '20 at 00:09
  • What I'm saying is not that you specifically will discover these tricks, but that if 1000 mathematicians study an area obsessively then they will discover anything in that area that is waiting to be discovered. But you yourself will also absorb and internalize many such tricks just by learning more and more math. For example, I've learned that that particular binomial identity is very fundamental, so whenever I'm staring at something involving binomial coefficients I might be tempted to try to use it if it fits. Maybe you'd like reading contest math books which are filled with clever tricks. – littleO Mar 19 '20 at 00:14
  • @littleO: good comment! Polya's "How to Solve it" is another relevant reference. – Rob Arthan Mar 19 '20 at 00:17
  • 1
    @Jair, I screenshoted the proof, Its my cursor. – Battlefrisk Mar 19 '20 at 00:17
  • @Battlefrisk Ahah! That explains why I couldn't find it in detexify. – Jair Taylor Mar 19 '20 at 00:20
  • @RobArthan I'll check that text out. – Battlefrisk Mar 19 '20 at 00:23
  • @littleO I'll check that out as well. – Battlefrisk Mar 19 '20 at 00:23
  • @Rob Arthan, I think the summand indexed by $i=0$ can be deleted because it is zero, because of the factor $i^k$, which is equal to $0^k$, which is equal to $0$. – Simon Mar 19 '20 at 02:01
  • @Simon: that was my my point, but I made a couple of typos that obscured the point. Thanks for the correction. N.b. it relies on $k > 0$. – Rob Arthan Mar 19 '20 at 19:28
  • Good point. And this will hold for us - since we're computing the mean and variance, we'll need $k=1$ and $k=2$. – Simon Mar 19 '20 at 20:41

0 Answers0