It is narrated from Nafi' (may Allah have mercy on him) that Sayyiduna Ibn Umar (may Allah be pleased with them both) had some work with Sayyiduna Muawiyah (may Allah be pleased with him). When he intended to write a letter, people said: Begin with his name. They kept insisting until he wrote: «بسم الله الرحمن الرحیم», to Muawiyah.
Hadith Referenceالادب المفرد / كتاب الرسائل / 1124
Hadith Gradingالألبانی:صحيح
Hadith Takhrij«صحيح : أخرجه ابن أبى شيبة : 25889 و البيهقي فى الكبرىٰ : 130/10»