A budget is both the total amount available to you and how you should spend it.
So, yes, your assumption is correct about the linear nature of the XP budget for encounters.
Target XP Reward, p.57 DMG
To find your total XP budget, multiply the number of characters in the party by the XP value of a monster whose level is equal to the encounter level you chose.
The encounter level isn't necessarily equal to the character level; normal encounters are party level or level+1, hard ones are higher, easy ones are lower. I believe you can step down to 75/50 XP for a "level 0" or "level -1" encounter.
The problem is that spending this budget on a single monster is going to be stone-boring. 4E is an active tactical game, not a cat-and-mouse simulator. Later advice in the DMG2 (pp. 50-51) suggests you keep the total number of monsters about the same as you would for a 4-5 player party, no matter your party size, for this reason.
Does that mean the first couple levels are just going to be Minion Town? Well, not necessarily. You might want to consider:
- Level 0 monsters. Just step back a level 1 monster's attacks, defenses, and damage by 1 point and knock a handful of points of HP as appropriate by role. A level 0 monster and 2 level 1 minions is 125 XP, a fairly even-level encounter for a level 1.
- Companions. Mentioned in the first DMG, they get a more extensive treatment in DMG2 starting at page 27. A companion is basically a friendly monster (including "monsters" like the listed entries for dwarves and humans) that basically contributes its total XP to every encounter's XP budget and gets it back as a share from combat, meaning the total amount of XP awarded per encounter doesn't change. A companion of your solo PC's level basically gives you 2 PCs' worth of budget for every encounter, which is a little more leeway to spend on interesting setups.
And, like p.57 of the DMG also suggests, try and keep the level range of the monsters you put in the combat within four or five levels of the PCs. Otherwise the numbers are going to slope too strongly one way or the other to be worth it.