The 9V batteries that Paul ghosts are fine for a short classroom demonstration, but the mAh rating of the 9V battery is so low that it would have to be replaced daily. Not very practical for a working project. A better solution would be to use a 12V battery (like a 4S LiPo) and a DC-DC buck converter to get 5V for the Arduino board.
Batteries in parallel is risky because no two batteries are identical. One would have slightly more potential then the other, and depending on the chemistry of the battery you could either have wasted energy in heat or, unlikely, a catastrophic meltdown.
Trucks and trailers do often put lead-acid batteries in parallel, but lead-acid batteries are more tolerant of a small imbalance.