Entropy of enhanced image more than the original image
According to me, the above relation should always hold true,


According to the data processing theorem (and here), this is always true.


  how can an enhanced image contain more information than the original image [?]


It cannot. A trivial example is that of interpolation. Suppose that you upsample an image by a factor of 2. This means, inserting a "new" pixel between two known ones. The information remains the same though because no "new light" has been captured. We still do not know what exactly happened BETWEEN the known pixels. All we can do effectively is INTERpolate. 

Interpolation works out the values of the unknown pixels based on the values of the KNOWN pixels, therefore re-distributing information across a larger surface. Since all processing takes place over the CAPTURED data it cannot but be inferred that a data processing step can only DECREASE the information content of a dataset.


  I have just seent that E2 will be greater than E1 if we enhance the image using CLAHE technique i.e the entropy of the enhanced image will be greater than the original image.


First of all, you are comparing two entropy measures that appear to have no relationship between them, no shared context. 

Having said this, is there any imaginable case in which $E2 &gt; E1$?

Consider the processing step as a black box. It accepts an image ($I$) and it produces an image ($O$), only that in this case, all that this black box does is $O = \alpha \cdot I + (1-\alpha) \cdot N(I)$, where $N(I)$ is a noise process that produces a two dimensional noise image with the same dimensions and overall brightness as $I$. The parameter $\alpha$ determines how much image and how much noise is mixed in the output.

So, at $\alpha = 1$, $O$ is essentially exactly the same as $I$. In this case $E(O) \le E(I)$. BUT, at $\alpha = 0$, $O$ is simply a noise image. An incoherent set of pixels whose entropy is very high. Since there is absolutely no relationship between $I$ and $N$, then it can well be that $E(O) &gt; E(I)$ but this does not mean that anything NEW (AND meaningful) was added to the image.

In the place of $N$ we could also have had extraneous information. For example, image from one camera being cross referenced with an image (of the same scene) from another camera.

But, there is also something else that is at play in your case and this is a "simplistic" view of entropy.

Before we move on to CLAHE, here is a simple experiment. I am using Octave, you can try it in MATLAB or anything else with a bit of re-writing:

n=1500;nBin=16;maxNum=32;
a=round(rand(1,n)*maxNum);
Q = hist(a,nBin)./sum(hist(a,nBin));
H = -sum(Q.*log2(Q)) 


Where n is the length of a random sequence, nBin is the number of histogram bins, a is a quantised sequence of random numbers up to maxNum, Q is the normalised marginal probability of a and H is the calculated entropy of a.

Now, for a given n,maxNum produce a sequence a and then calculate its Shannon entropy for two different nBin, say for instance nBin=16 and nBin=32.

To recap, SAME sequence of numbers a (absolutely no processing), two DIFFERENT histogram resolutions. What are the two different H?

About 4 for nBin=16 and about 5 for nBin=32. Isn't this a bit suspicious, given that $2^4=16$ and $2^5=32$?

Shannon's entropy gives you the upper bound of the entropy of a source and the way it is derived here, assumes that all the characteristics of the source are captured in Q. Function rand returns numbers from a uniform distribution. If you divide the sequence's histogram at 2 levels, you get 2 equiprobable events and still need 1 bit to describe them (try it, for nBin=2). If you divide the histogram of the SAME sequence at 4 levels, you now get 4 EQUIPROBABLE events for which you need 4 bits to describe them. At 5 levels of the SAME sequence you now get.....and so on.

In this example, a remained the same but the expression of entropy changed, purely as a byproduct of how we calculated it.

This way of calculating the entropy suffers from another problem. That of "empty" bins. If you get a bit more adventurous in the above example and set nBin=500 (for example), you will notice that your H might come back as NaN. Once the histogram contains zero bins, log2(0)*0 produces NaN. Again, we get a result which is purely based on the way entropy is calculated. You might say, "I will omit the zero entries" but then again, you might be omitting them in one image because they did not happen but you would not be able to ignore them in another image because they DID happen.

And THIS is what you see in your case, as a byproduct of how adaptive equalisation works.

Your initial $I$ has a given histogram "shape", a given distribution of grey tones. Most likely this is concentrated around a lobe inside a limited region at the low end. Its entropy will appear low. Yes, you don't need many bits to describe this lobe. AFTER equalisation, the algorithm has now redistributed grey values all over the place, therefore it results in a WIDER histogram (with also differences in its overall shape, with tones that now are not 'negligible') appearing to have a higher entropy. Appearing to require MORE bits to describe the "new" states.

Shannon's entropy is not the only way to calculate entropy. There are other definitions as well, such as those that work over the spectrum of the image or based on data compression.