A validation rule, however will not solve your purpose. Before we go ahead we need to address this "What is duplication of a record?".
Answer: it depends on the requirement. It could mean if two fields have repeated values for two records or one field repeated or could very well mean 4 -6 fields repeated with similar values
If it was a single field that determines your duplication, then you can make the field unique and avoid duplication.
Let us address for those who need to take into account say 2 or more fields into account to consider as duplicate record.
Say for example, in account record if account name and account numbers are same for two account records then they are duplicates.
If one thinks logically, this requires querying in the data base to see if such record already exists.
However, We can achieve this using configuration only.
1. Create a text field which should be marked unique.
2.You need to write a workflow that runs on create and edit criteria. Update your field created in step one. Use formula to take the new value . It should concatenate all your required fields in it. For example : Account Name & Account Number
This will prevent duplicates and you will not have to clean up your org on a regular basis :-)