Which compound algorithms would weaken cipher, not strengthen it? OK, in school, some of the lecturers always say "if you compound the crypto, it may make the cipher weaker".

So, which combinations of algorithms would do this? Why? Can anyone show the mathematical proof?

For example, would RSAk1(AESk2[AESk3[x]]) make the encrypted x weaker? Assuming all keys used are different and randomly generated using a SecureRandom function.
Moving my reply from the comments into a proper answer. The general case of double-encrypting is formally explained by Yehuda Lindell in this answer on crypto.SE. Summing up:


Same Algorithm, same key: It may or may not be secure, depending on the properties of the cipher. It is definitely not always secure, but may be secure for practical cases.
Same Algorithm, different keys: Secure, because otherwise people who do not know the key could break the encryption by encrypting with a different key, which would be... strange, and not very logical.
Different Algorithms, different keys: Secure, for the same reason. Otherwise, sending PGP-encrypted eMails over a TLS connection would be unsafe, which would be ridiculous.
Different Algorithms, same keys: Insecure. Never reuse keys for different encryption algorithms (even when not double-encrypting). For example: If you are using the same RSA keys to sign and encrypt, and the adversary can get you to sign a value for them, it can use you to decrypt data, because signature = encryption with the private key = decryption of data encrypted with the public key.


Summing things up: "Don't double encrypt" is a pretty general hint that definitely doesn't always apply, but it serves as a good baseline to avoid critical mistakes. The more nuanced version is "Don't reuse keys for different algorithms, and to be sure, don't double-encrypt with the same key and algorithm, either, it may hurt you".