Musannaf Ibn Abi Shayba 36:369

'Abd al-Rahim ibn Sulayman narrated to us, from Zakariya ibn Abi Za'ida, who said: I was with Abu Ishaq between Mecca and Medina, and a man from Khuza'a traveled alongside us. Abu Ishaq said to him: "How did the Messenger of Allah, may Allah bless him and grant him peace, say: 'This cloud has thundered with the victory of Banu Ka'b'?" The Khuza'i said: "It has indeed arrived with the victory of Banu Ka'b." Then he brought out to us the letter of the Messenger of Allah, may Allah bless him and grant him peace, to Khuza'a, and I wrote it down that day. It contained: "In the name of Allah, the Most Gracious, the Most Merciful. From Muhammad, the Messenger of Allah, to Budayl, Busr, and the chiefs of Banu 'Amr. I praise to you Allah, besides whom there is no god. To proceed: I have not sinned against you, nor have I been negligent regarding your affairs. You are the most honorable of the people of Tihama to me, and the closest in kinship, along with those who follow you and the Mutayyabin. I have taken for those who emigrated among you the same as I have taken for myself, even if he emigrated from his land, not residing in Mecca except as a pilgrim for 'Umrah or Hajj. I have not been negligent regarding you if you have submitted [to Islam], and you shall not be disappointed by me, nor restricted. To proceed: 'Alqama ibn 'Ulatha and the sons of Hawdha have submitted, pledged allegiance, and emigrated, along with those who followed them from 'Ikrimah. He took for those who followed him the same as he took for himself, and they are part of one another in what is lawful and what is unlawful. By Allah, I have not lied to you, and may your Lord give you life." He said: It reached me from al-Zuhri that he said: "These are Khuza'a, and they are of my family." He said: The Prophet, may Allah bless him and grant him peace, wrote to them while they were at that time dwelling between 'Arafat and Mecca, and they had not yet submitted to Islam when he wrote to them, and they were allies of the Prophet, may Allah bless him and grant him peace.