Symbolic calculation in two variables.

[caffeinemachine]

The following is identically 0 which can be readily checked by a simple hand calculation.

$\binom{n+1}{k}2^{-n-1} - \binom{n}{k}2^{-n} + \binom{n}{k}*2^{-n-1} - \binom{n}{k-1}2^{-n-1}$

If you enter this in SAGE or Mathematica, using the appropriate script, and use full_simplify() and FullSimplify[] respectively, you will find that both of these softwares show you the result 0.

Can somebody tell me how does a computer handle such expressions symbolically?

 

[Klaas van Aarsen]

The following is identically 0 which can be readily checked by a simple hand calculation.

$\binom{n+1}{k}2^{-n-1} - \binom{n}{k}2^{-n} + \binom{n}{k}*2^{-n-1} - \binom{n}{k-1}2^{-n-1}$

If you enter this in SAGE or Mathematica, using the appropriate script, and use full_simplify() and FullSimplify[] respectively, you will find that both of these softwares show you the result 0.

Can somebody tell me how does a computer handle such expressions symbolically?

A computer program matches and applies a long list of pre-programmed formulas.
It can brute force the possible implication steps and see where it gets.
Its algorithms will prefer simpler results over complicated results, although it will ultimately search all of them (until it times out).

In your current problem the following rules apply:

1. Isolate a common factor. In your case $2^{-n-1}$ and $\binom{n}{k}$ can be isolated.
2. Evaluate sub expressions containing only numbers.
3. Apply $\binom {n+1} k = \binom n {k-1} + \binom n k$.

When we apply them exhaustively the result zero rolls out.
Your problem is simple enough that you can still do this by hand as well, emulating what the computer will do.