Disprove that "if $p$ is a prime number, then $2^p-1$ is also a prime number"? We can see manually that $2^p-1$ is not prime. As $2047$ is not a prime. $2^{11} = 2048$.
But I'm unable to figure out a formal way of disproving the statement.
 A: To disprove an assertion that is false, a single counterexample suffices, and in this particular case, you've already provided it: $$2^{11} - 1 = 2047 = 23 \times 89.$$
This is formal enough. For professional mathematicians, the simplest, minimal way to accomplish the goal is the best way, as evidenced in the old joke about the mathematician who escaped what Houdini could not by redefining "inside" and "outside."
But if you want, you can add some additional remarks and make it formal by prefacing it with the word "remark." For example:

Remark. The largest known Mersenne prime as of this writing is $2^{74207281} - 1$, which is believed to be the $49^{\textrm{th}}$ Mersenne prime. Given that $74207281$ is the $4350601^{\textrm{st}}$ prime, this suggests that almost any prime $p$ will fail to give a prime of the form $2^p - 1$.

A: Here is a possible general proof:
If prime numbers are randomly distributed, as is widely and strongly believed, then $x=2^p-1=prime$ is false.
Proof:
Assume $p_s$ is the smallest possible prime. Then, $x=2^{p_{s}}- 1$ must be the next prime. This means that $x$ determines the next prime in the sequence and so forth. This contradicts the fundamental belief that prime numbers are randomly distributed.
If a prime number lies between $p_s$ and $x=2^{p_{s}}- 1$, then this contradicts $p_s$ being the smallest prime because something smaller than $p_s$ would have to construct that interim prime. Also, something smaller than $p_s$ would have to exist in order to construct $p_s$ via the same pattern.
A: If $p$ is a prime of the form $4k+3$, such that $2p+1$ is also prime, it can be proven that $2p+1|2^p-1$.
So you have a family of primes being a counterexample to the claim.
It is conjectured, but not proven, that infinite many primes $p=4k+3$ exist, such that $2p+1$ is also prime.
A: You could also do a proof by contradiction (which in this case would only be a more formal way to phrase your proof).  
In this method you start by assuming that the opposite of what you want to prove is true (in our case, assuming that $2^p - 1$ is a prime). Given what we know, 2047 should be prime, because it follows the form of $2^p - 1$.  
However, we can see that:  

$2^{11} - 1 = 2048 - 1 = 2047$  

We know 2047 is not a prime number, because 2047 = 23 * 89.  
Now we have reached the contradiction part of the proof. According to our assumption in the beginning of the proof, any number of the form $2^p - 1$ should be prime. We have just shown this assumption to lead to a contradiction, and thus we must abandon this assumption as false. 
A: You've demonstrated a counterexample, so it is a formal proof.
All you need to write is something like "The statement is false: p=11 is a prime, but $2^{11} - 1= 23 \times 89$ is not prime."
Trying lots of cases is a valid technique to disprove something (but not necessarily to prove something unless you can do a complete exhaustive search or show a reduction to a set where you can exhaustively search; a decent number of combinatorics/algebra proofs have been done by reducing to a set of (many) cases and then exhaustively checking those cases via computer). 
