Inspired by Paul Lockhart's "A Mathematician's Lament".
I would argue that what students actually need is play. Play is essential for learning especially at the earliest stages of education. Given that the central element of mathematics is proof, this means that students should form their own conjectures from an early age. They should also attempt to justify them using a verbal explanation (ideally without much mathematical jargon which the child does not understand yet).
Contrast this with how we currently teach students: start by assuming these facts as a given, and then force students to memorise them through rote-and-drill repetition. This is the complete opposite of what we should be doing. Rather, students should firstly ask the right questions, for example by drawing a semicircle, and then wondering what happens to the angle inscribed in it as the point moves. Then they will ponder, struggle, try and then try again, before they might make another copy and discover a rectangle hidden within the circle:
Aha! Since we made a copy of the triangle, each pair of opposite lengths must be the same, so we have a rectangle! Therefore the angle inscribed in a semicircle is 90º!
This is how we make students engage with mathematics, discovering the intrinsic value of truth and beauty hidden within it.
Students need real experience with mathematics through inquiry and through play before they can progress with applying the same methods to harder problems, or manipulating different methods of proof such as proof by induction. In other words, students need to have lots and lots of fun with mathematics.
Even in high school curricula where mathematical investigation and reasoning are given significant attention such as the IB Diploma, used in many international schools around the world, investigation is treated as a subject in isolation, divorced from the rest of the course. Students are guided through a bewildering assortment of topics throughout the course where mathematical concepts are seen as disparate and disconnected. Investigation is limited to a month or two where students start from scratch, particularly those that have come from more traditional curricula. After 12 years of rote memorisation, of seeing mathematics as a game where symbols are manipulated as if by magic, no wonder students come to struggle with mathematics later. If all they have seen are grammar and conjugation drills in their English class, how will they be equipped to write and read stories, plays, novels and poems, just as they will engage with the art of proof?
In mathematics, communication is key and notation is secondary. All of those pesky symbols: $\alpha, \beta, \gamma, \Sigma, \Pi$ can come later. And so students need to get in the right frame of mind as viewing mathematics as a narrative, with an inherent narrative structure of exposition, discovery and conclusion, not as a meaningless bash of symbols. We do the exact same thing with English, or students' native languages.
So for students who have been completely deprived of this throughout their "education", we need to start small. Students will naturally be horrified at the sight of a research paper as it will be shockingly new. Start by using very simple yet perplexing examples: why does a pyramid take up a third the space of the cuboid bounding it? They will very often not know why. Spend as much time with them as possible, no matter how long it takes for them to understand. Tell them that mathematics is like any work of art or music in its beauty and its lack of relevance in the real world. First give them as much space and time to make mistakes, to ask "what if?". Gently prompt them in the right direction when they get lost, which will involve the destruction of many assumed truths that they may hold sacred. You will need to hold their hand (yes, even in undergrad) and then let go when they are ready.
This will mean forgetting what you already know about teaching. Get them to chat to each other, present their work on the whiteboards, get up from your lectern and wander around the room (if you haven't already). And you will give them the power of independent thought and autonomy, divorced from any pressure about passing grades or graduation requirements. Because that is what it means to be a great teacher and a friend, a great mentor and a learner, and what it means to play. Make your classroom as unbounded as the imagination and curiosity of students. And in time they will learn to write.